洛谷P3132 [USACO16JAN]Angry Cows G 题解

洛谷P3132题解

【题目描述】

奶牛Bessie设计了一个游戏：“愤怒的奶牛”。游戏的原型是：有一些可爆炸的草堆分布在一条数轴的某些坐标上，玩家用弹弓把一头奶牛发射到数轴上。奶牛砸到数轴上的冲击波会引发附近的草堆爆炸，而被引爆的草堆可能会引爆其他草堆。游戏的目标是玩家用一只奶牛炸掉所有的草堆。

有N个草堆在数轴的不同位置，坐标为 x 1 , x 2 , … . , x n x_1,x_2,….,x_n x1,x2,….,xn。如果玩家以能量$R$把奶牛发射到坐标$x$，就会引爆半径$R$及以内的的草堆，即坐标范围$[x-R,xR]$的草堆都会燃爆，每个被奶牛引爆的草堆又会2次引爆半径$R-1$及以内的的草堆，2次引爆的草堆又会3次引爆半径$R-2$及以内的的草堆…直到一次引爆后没有其他草堆被波及或半径为0。

现在只有1头奶牛，请计算如果要引爆所有的草堆，最小的R是多少？

现在是2022/1/27，这道题是我目前为止做过的最好的一道贪心加二分的题，思路很巧妙。

我一开始做的时候把这道题想得太简单，贪心策略是扔到中点然后再模拟，只能过掉样例。

这道题的正解巧妙之处在于，它没有纠结于奶牛的落地位置和后面的模拟操作，而是另辟蹊径，考虑爆炸之后的边界点，并且通过预处理代替模拟来判断当前的$R$可不可行，下面详细说一下。

首先定义两个数组：

1. $f[i]$：表示以$i$为爆炸后的左边界，能够覆盖掉前$1\sim i-1$个草堆所需要的最小半径
2. $g[i]$：表示以$i$为爆炸后的右边界，能够覆盖掉$i1\sim n$个草堆所需要的最小半径

那么对于$f$和$g$，有一个非常明显却又十分重要的性质：$f$随$i$的递增而增大，$g$随$i$的递增而减小。于是，在check的时候，我们只需要从大到小枚举左边界$i$，当遇到第一个满足$f[i]1\le R$的$i$时，开始枚举右端点$j$；对于满足$a[j]-a[i]\le 2\ast R$的右端点$j$，如果$r[j]1\le R$，那么直接返回true。$f[i]1\le R$这一步的原因是：$i$是被枚举的左边界，因此接下来$R$会减$1$，那么$f[i]$的定义是能够覆盖掉前$1\sim i-1$个草堆所需要的最小半径，如果$f[i]\le R-1$，则说明左边所有的草堆可以被后续的爆炸覆盖掉，$g[j]$同理。乍一看这是个 O ( n 2 ) O(n^2) O(n2)的复杂度，但是我们可以在$i$的那层循环加一个break，原因是如果对于最大的满足$f[i]1\le R$的$i$，我们都没有找到符合条件的$j$，那么你的$i$继续小，根据$g[i]$随$i$的减小而增大的性质我们知道更不可能有满足条件的$j$了，因此直接break然后return false即可。

bool check(double R) {
    for(int i = n; i >= 1; --i) {
        if(f[i]   1 <= R) {
            for(int j = i; j <= n;   j) {
                if(x[j] - x[i] > 2 * R) continue;
                if(g[j]   1 <= R) {
                    return true;
                }
            }
            // 对于最大的符合条件的i，没找到右端点，那么直接跳出循环，因为更小的i更不可能找到右端点
            break;
        }
    }
    return false;
}

接下来就是重头戏，怎么预处理出$f$和$g$，其实这个部分有点DP的味道。我们考虑对于$f[i]$，它可以有哪些情况？其实只有两种：

1. $f[i]=f[j-1]11\le j\le i$
2. $f[i]=a[i]-a[j-1]1\le i\le j$

最终的$f[i]=\max (f[j-1]1,a[i]-a[j-1])$。其实就是从$i$之前的某个草堆$j$转移过来，如果是$f[j-1]1>a[i]-a[j-1]$，那么我们让$f[i]=f[j-1]1$一定能炸到$j$，然后$R$变成$f[j-1]$，显然可以从$j-1$炸到$1$；如果是$f[j-1]1<a[i]-a[j-1]$，那么让$f[i]=a[i]-a[j-1]$，显然能炸到$j$，然后根据不等式我们知道$R$减一后依然是大于$f[j-1]$的，所以也能从$j-1$炸到$1$。

从函数的角度来理解，$f[j-1]1$是一个增函数，$a[i]-a[j-1]$是一个减函数，因此我们的$f[i]$应该在两者交界处取得。这个部分朴素做法是 O ( n 2 ) O(n^2) O(n2)，但是因为是单调的，因此可以用二分优化到$O(nlogn)$。$g$和$f$是同理的，只是不等式方向变了。

void preprocess() {
    f[1] = 0;
    for(int i = 2; i <= n;   i) {
        int l = 1, r = i;
        while(l   1 < r) {
            int mid = (l   r) >> 1;
            if(f[mid - 1]   1 < x[i] - x[mid - 1]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        // 这里是进一步逼近，因为我们的l和r是希望能够表示j的一个可行区间，因此我们不希望二分结束的时候是l大于r，于是就在
        // 二分的时候多放缩了一个1，导致最后l 1=r，所以我们最后需要判断一下l好还是r好
        f[i] = min(max(f[l - 1]   1, (double) x[i] - x[l - 1]), max(f[r - 1]   1, (double) x[i] - x[r - 1]));
    }

    g[n] = 0;
    for(int i = n - 1; i >= 1; --i) {
        int l = i, r = n;
        while(l   1 < r) {
            int mid = (l   r) >> 1;
            if(g[mid   1]   1 < x[mid   1] - x[i]) {
                r = mid;
            } else {
                l = mid;
            }
        }
        g[i] = min(max(g[l   1]   1, (double) x[l   1] - x[i]), max(g[r   1]   1, (double) x[r   1] - x[i]));
    }
}

至此本题的核心部分全部结束，真的是一道非常好的题目。

这篇好文章是转载于：学新通技术网