题意简述
给出一个长度为 $n$ 的序列 $h$，其中的每一项代表第 $i$ 座建筑物的高度。
当 $hi > h{i-1}$ 且 $hi>h{i+1}$ 时，称第 $i$ 座建筑是“凉爽的” 。
注意，第一座建筑和最后一座建筑不可能为“凉爽的”。
你可以增高任何一座建筑物的高度，使得最终“凉爽的”建筑物最多。
为了使“凉爽的”建筑物最多，求出需要增加的最小总高度。
多测。 $3 \leq n \leq 10^5,1\leq h_i \leq 10^9$。
算法分析
首先考虑在什么情况下“凉爽的”建筑物是最多的。
由于“凉爽的”建筑的定义，我们知道不会存在连续的“凉爽”建筑。
由于第一座和最后一座建筑一定不是“凉爽的”，所以最终“凉爽的”建筑数为 $\left\lceil \dfrac{n}{2} \right\rceil - 1$。
事实上，这个结果实际上是分类讨论得出的：
- 若 $n$ 为偶数，可知最多有 $\dfrac{n-2}{2}$ 座建筑是“凉爽的”。
- 若 $n$ 为奇数，可知最多有 $\dfrac{n-2+1}{2}$ 座建筑是“凉爽的”。
这个结论过于显然，就不举例了。
下一步考虑应该令哪些建筑物是“凉爽的”。
对于 $n$ 是奇数的情况，“凉爽的”建筑的位置是固定的。令这些位置的建筑的高度高于两侧建筑高度的最大值即可。
对于 $n$ 为偶数的情况，情况会稍微复杂一些：
这里令 $1$ 代表“凉爽的”建筑，令 $0$ 代表非“凉爽的”建筑。
在纸上写一写就会发现，符合题意的序列并不是唯一的。
比如 $n=8$ 时就有如下几种情况：
1
2
3
4
| - 1 0 1 0 1 0 -
- 1 0 1 0 0 1 -
- 1 0 0 1 0 1 -
- 0 1 0 1 0 1 -
|
但是，通过观察这四个序列，我们能发现一些规律：
去掉第一项和最后一项，中间的每两个分成一组，每组一定是 1 0 与 0 1 其中之一。
对于这些组，一定是前一部分是 1 0 ，后一部分是 0 1 ，并且仅会在整个序列中间更改一次顺序。
因为 $1$ 的左右两边一定是 $0$ ，所以 0 1 后面不能接 1 0 ，1 0 前面也不能是 0 1。
所以我们可以事先求出全是 1 0 的花费前缀和，求出全是 0 1 的花费后缀和，最后枚举在第 $k$ 组改变了顺序求最小值即可。
对于每个测试用例，复杂度为 $O(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
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
60
61
| #include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5;
typedef long long ll;
int B[maxN];
ll A1[maxN];
ll A2[maxN];
int main(){
int T;
scanf("%d",&T);
while(T--){
int N;
scanf("%d",&N);
for(int i = 1;i<=N;i++) scanf("%d",&B[i]);
ll ans = 0;
if(N & 1){
for(int i = 2;i<N;i+=2){
int M = max(B[i-1],B[i+1]);
if(B[i] <= M){
ans += (M+1-B[i]);
}
}
}else{
memset(A1,0ll,sizeof(A1));
memset(A2,0ll,sizeof(A2));
int cnt = 1;
for(int i = 2;i<N-1;i+=2){
int M = max(B[i-1],B[i+1]);
if(B[i] <= M){
A1[cnt] = A1[cnt-1] + (M+1-B[i]);
}else{
A1[cnt] = A1[cnt-1];
}
cnt++;
}
cnt = (N>>1)-1;
for(int i = N-1;i>2;i-=2){
int M = max(B[i-1],B[i+1]);
if(B[i] <= M){
A2[cnt] = A2[cnt+1] + (M+1-B[i]);
}else{
A2[cnt] = A2[cnt+1];
}
cnt--;
}
int r = (N >> 1);
ans = 1e17;
for(int i = 1;i<=r;i++){
ans = min(ans,A1[i-1]+A2[i]);
}
}
printf("%lld\n",ans);
}
return 0;
}
|