炸弹

Posted on Edited on In

题目大意：有𝑛个炸弹分布在一条数轴上。现在需要玩家以一定的能量引爆某一个炸弹，而炸弹爆炸会引起连锁 反应导致更多的炸弹爆炸。炸弹爆炸时会携带能量𝑋，可以引爆和他距离≤ 𝑋的所有炸弹。当一个炸弹被能量𝑋的爆炸引爆时，该炸弹会带\(⌊\dfrac {2x} 3⌋\)(下取整)的能量。玩家可以设置第一个引爆的炸弹的能量，现在请问，如果想引爆所有炸弹，第一个引爆的炸弹的能量最少是多少呢？数据量1e6，开两秒

一眼看上去就像是二分

考场上的二分写爆炸了，sb样例，太水了

正解是单调队列优化dp

\[f_i = min(max(\dfrac {2f_j} 3,a[i]-a[j])),(j<i)\]

可得60分（裸的二分也可以60分）

裸的二分是来二分这个能量，然后放回原数组中\(O(n^2)\)判断（每一个位置都作为引爆的起点）

观察发现，我们使得起点在中间的某一段选取，显然要比在两端点选取要更优

并且还得到一个显然的结论，对于一个选定的端点，在其两侧是具有单调性的

有单调性就意味着二分是合理的

然后就可以在二分里面套一个二分

复杂度\(O(log^2n)\)

至此，一个暴力的做法，成功把一个单调队列优化dp的题目卡了过去

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];

int check(int p)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        int s = mid, now = p, res1 = 1, res2 = 1;
        for (int i = s - 1; i >= 1; i --)
        {
            if (a[s] - a[i] > now)
            {
                if (s == i + 1) {res1 = 0; break;}
                else {s = i + 1, now = 2 * now / 3, ++ i;}
            }
        }
        s = mid, now = p;
        for (int i = s + 1; i <= n; i ++)
        {
            if (a[i] - a[s] > now)
            {
                if (s == i - 1) {res2 = 0; break;}
                else {s = i - 1, now = 2 * now / 3, -- i;}
            }
        }

        if (res1 && res2) return true;
        if (! res1 &&! res2) return false;
        if (! res1) r = mid - 1;
        else l = mid + 1;
    }
    return false;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i ++) a[i] = read();

    sort(a + 1, a + n + 1);

    int l = 0, r = a[n];

    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d", l);
    return 0;
}