# BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

## Sol

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, a[MAXN], q[MAXN], Cro[MAXN];
double P[MAXN], sqr[MAXN];
double calc(int j, int i) {
return a[j] + sqr[i - j];
}
int K(int x, int y) {
int l = max(x, y), r = N, ans = N + 1;
while(l <= r) {
int mid = l + r >> 1;
if(calc(x, mid) >= calc(y, mid)) l = mid + 1;
else r = mid - 1, ans = mid;
}
return ans;
}
void solve() {
int h = 1, t = 0;
for(int i = 1; i <= N; i++) {
while(h < t && K(q[t - 1], q[t]) >= K(q[t], i)) t--;
q[++t] = i;
while(h < t && K(q[h], q[h + 1]) <= i) h++;
P[i] = max(P[i], calc(q[h], i));
}
}
main() {
for(int i = 1; i <= N; i++) a[i] = read(), sqr[i] = sqrt(i);
solve();
reverse(a + 1, a + N + 1);
reverse(P + 1, P + N + 1);
solve();
for(int i = N; i >= 1; i--)
printf("%d\n", max(0, (int)ceil(P[i]) - a[i]));
return 0;
}

1811 篇文章122 人订阅

0 条评论

## 相关文章

### 数据挖掘知识脉络与资源整理(十)–箱线图

? ? 箱线图的简介 箱形图（Box-plot）又称为盒须图、盒式图或箱线图，是一种用作显示一组数据分散情况资料的统计图。因形状如箱子而得名。在各种领域也经常...

34680

35340

### 当七夕遇上算法竞赛

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去T...

15520

11730

11600

29660

24720

22410

1.6K80

28940