题面链接

Updated on 2020-05-02 11:37(增加正解并修改标题)

不能 AC 的做法

60 分

枚举每个炸弹然后二分答案,复杂度显然为 $O(n^2\log k)$,只适用于 60% 的数据。

70 分

⚠警告:这里使用了玄学⚠

设一函数$f(x)$表示在 x 这个位置点燃炸弹的最小能量。

我们不妨大胆猜想:$f(x)$是个单峰函数。(实际上并不是)

于是写出三分套二分,对拍一组数据发现结论错误(悲

不过对于 60% 的数据暴力能过,对于剩下的 40%,我们错了不亏,对一个血赚。考虑使用namespace开两个 subtask 分别求解。

于是多了 10 pts(并且我就凭着这 10pts 打赢了皇帝

这里就是我的考场代码了:MZOJ submission #8290

80 分

分析我们的 60% 做法差在何处。

每次二分都需要进行一次$O(n)$的模拟,就慢在这里了。

于是我们考虑进行一些压缩。

设$f(x)$表示这个点向前炸的最小能量,$g(x)$表示这个点向后炸的最小能量。

现在考虑如何求$f(x)$。

看出$f(x)$是个单调函数。(未经证明,如果这里都错了就真的玄学了)

当我们求$f(i)$时,必然已经求出了$f(1), f(2), f(3),…, f(i-1)$,所以我们对爆炸能量(记为$X$)进行二分答案,再对能炸到的最前面的点进行二分查找(记为$k$),比较$f(k)$和$\lfloor\dfrac{2X}{3}\rfloor$的大小关系。

会出现以下三种情况:

  • 能量过小,一个点都炸不到
  • $f(k)>\lfloor\dfrac{2X}{3}\rfloor$
  • $f(k)\leq\lfloor\dfrac{2X}{3}\rfloor$

应对策略显然分别为:

  • $l=mid+1$
  • $l=mid+1$
  • $r=mid-1$

$g(x)$同理来求。

最后一个循环,求出$ans=\min (\max(f(i), g(i)) )$

时间复杂度为$O(n\log k\log n)$。

于是又多了 10pts,剩下 20% 死于 TLE。

不正确的 AC 做法

我们仍然秉承着“错了不亏,对了血赚”的原则。

对于$O(n\log k\log n)$可以通过的数据,我们跑暴力。

其他的 20 分稍作修改:

我们将求$f(i),g(i)$的范围分别缩小到原来的$\dfrac{2}{3}$

即:求出$f(i),i\in[1,\lfloor n\times2/3\rfloor]$和$g(i),i\in[n-\lfloor n\times2/3\rfloor,n]$。

$ans=\min{\max(f(i), g(i))},i\in [n-\lfloor n\times2/3\rfloor, \lfloor n\times2/3\rfloor]$。

因为造数据的没想到有这么乱搞的做法,所以 AC 了。

代码

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 + 5;
int n, x[N], f[N], g[N], sum[N], suf[N], LL, RR;

inline int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

int main() {
n = get();
if(n >= 100000) LL = n * 2 / 3, RR = n - n * 2 / 3;
else LL = n, RR = 1;
for(register int i = 1; i <= n; i++) x[i] = get();
sort(x + 1, x + 1 + n);
for(register int i = 2; i <= LL; i++) {
int MaxN = x[i] - x[1];
int l = 1, r = MaxN, mid;
while(l <= r) {
mid = (l + r) >> 1;
int nx = x[i] - mid;
int L = 1, R = i - 1, Ans = -1;
while(L <= R) {
int Mid = (L + R) >> 1;
if(x[Mid] >= nx) Ans = Mid, R = Mid - 1;
else L = Mid + 1;
}
if(Ans == -1) l = mid + 1;
else if(floor(mid * 2 / 3) < f[Ans]) l = mid + 1;
else f[i] = mid, r = mid - 1;
}
}
g[n] = 0;
for(register int i = n - 1; i >= RR; i--) {
int MaxN = x[n] - x[i];
int l = 1, r = MaxN, mid;
while(l <= r) {
mid = (l + r) >> 1;
int nx = x[i] + mid;
int L = i + 1, R = n, Ans = -1;
while(L <= R) {
int Mid = (L + R) >> 1;
if(x[Mid] <= nx) Ans = Mid, L = Mid + 1;
else R = Mid - 1;
}
if(Ans == -1) l = mid + 1;
else if(floor(mid * 2 / 3) < g[Ans]) l = mid + 1;
else g[i] = mid, r = mid - 1;
}
}
int ans = 0x3f3f3f3f, pos;
for(register int i = RR; i <= LL; i++) ans = min(ans, max(f[i], g[i]));
cout << ans;
return 0;
}

附件

和正解的对比

丢人

这时间,丢人。

不过总算 A 了,这是好的。

正解

在 dottle 的启发下,我学会了正解。

我们再来分析 $O(n\log n\log k)$ 差在哪里。

$f[i]$ 继承的下标应该是可以直接 $O(1)$ 找到的,而我们使用了两次二分,就差在这里了。

所以现在的问题是:如何 $O(1)$ 找到 $f[i]$ 继承的位置。

显然 $f[i] = min\lbrace max(x[i] - x[k], \lceil \dfrac{3f[k]}{2} \rceil)\rbrace,k\in[1, i-1]$

由于坐标经过了排序,所以$x[i]-x[k]$单调不降。

前面已经说了$f[i]$ 单调不升,所以$\lceil \dfrac{3f[k]}{2} \rceil$同样单调不升。

对他们取最大值,相当于求一个单峰函数的最低点,这个最低点就是两个他们的交点。

这个交点可以二分求,但是不够快。

我们发现当 i 增加的时候,$\lceil \dfrac{3f[k]}{2} \rceil$会整体增加一个值,那么这个单调不升的函数会向上平移,则交点随着 i 的增加单调向右移动。于是我们可以维护这个交点的位置。

部分代码

1
2
3
4
5
for(register int i = 2; i <= n; i++) {
while(now < i - 1 && max(x[i] - x[now], (int)ceil(f[now] * 3.0 / 2)) >= max(x[i] - x[now + 1], (int)ceil(f[now + 1] * 3.0 / 2))) //尝试把交点向右移
now++;
f[i] = max(x[i] - x[now], (int)ceil(f[now] * 3.0 / 2)); //得到f[i]
}

由于 now 和 i 只会向右移动,所以这部分复杂度为 $O(n)$(略同于 Manacher 算法的时间复杂度证明)

但是很遗憾,快速排序占了大头,所以整体是 $O(n \log n)$

代码

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
#include<bits/stdc++.h>
using namespace std;

inline int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

const int N = 1e6 + 5;
int n, f[N], g[N], x[N];

int main() {
n = get();
for(register int i = 1; i <= n; i++) x[i] = get();
sort(x + 1, x + 1 + n);
int now = 1;
for(register int i = 2; i <= n; i++) {
while(now < i - 1 && max(x[i] - x[now], (int)ceil(f[now] * 3.0 / 2)) >= max(x[i] - x[now + 1], (int)ceil(f[now + 1] * 3.0 / 2)))
now++;
f[i] = max(x[i] - x[now], (int)ceil(f[now] * 3.0 / 2));
}
now = n;
for(register int i = n - 1; i >= 1; i--) {
while(now > i + 1 && max(x[now] - x[i], (int)ceil(g[now] * 3.0 / 2)) >= max(x[now - 1] - x[i], (int)ceil(g[now - 1] * 3.0 / 2)))
now--;
g[i] = max(x[now] - x[i], (int)ceil(g[now] * 3.0 / 2));
}
int ans = 0x3f3f3f3f;
for(register int i = 1; i <= n; i++) ans = min(ans, max(f[i], g[i]));
cout << ans;
return 0;
}

各解法对比

算法 得分 时间 空间 长度
三分套二分 70 3632ms 10724kb 2.3kb
玄学二分 100 5301ms 12008kb 1.5kb
正解 100 684ms 14460kb 1kb

所以说,代码越短,空间越大,时间越短,分数越高