[POI2011]Lightning Conductor
题面翻译
给定一个长度为 \(n\) 的序列 \(\{a_n\}\)，对于每个 \(i\in [1,n]\) ，求出一个最小的非负整数 \(p\) ，使得 \(\forall j\in[1,n]\)，都有 \(a_j\le a_i+p-\sqrt{|i-j|}\)
\(1 \le n \le 5\times 10^{5}\)，\(0 \le a_i \le 10^{9}\) 。
题目描述
Progressive climate change has forced the Byteburg authorities to build a huge lightning conductor that would protect all the buildings within the city.
These buildings form a row along a single street, and are numbered from 
to 
.
The heights of the buildings and the lightning conductor are non-negative integers.
Byteburg's limited funds allow construction of only a single lightning conductor.
Moreover, as you would expect, the higher it will be, the more expensive.
The lightning conductor of height 
located on the roof of the building 
(of height 
) protects the building 
(of height 
) if the following inequality holds:
where 
denotes the absolute value of the difference between 
and 
.
Byteasar, the mayor of Byteburg, asks your help.
Write a program that, for every building 
, determines the minimum height of a lightning conductor that would protect all the buildings if it were put on top of the building 
.
输入格式
In the first line of the standard input there is a single integer 
(
) that denotes the number of buildings in Byteburg.
Each of the following 
lines holds a single integer 
(
) that denotes the height of the 
-th building.
输出格式
Your program should print out exactly 
lines to the standard output.
The 
-th line should give a non-negative integer 
denoting the minimum height of the lightning conductor on the 
-th building.
样例 #1
样例输入 #1
6
5
3
2
4
2
4
样例输出 #1
2
3
5
3
5
4
题解
先只考虑转移点小于当前点的情况。
画出转移点关于i的函数，可以发现两函数之间最多只有一个交点。
于此，可以得出二分栈做法或者决策单调性（四边形不等式也可以证）。
有决策单调性不要死证，可以画图辅助证明/打表/感性理解都是好的做法。
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=500010;
int n,sum[N];
double sq[N],f[N];
void deal(int l,int r,int L,int R){
if(l>r)return ;
int mid=(l+r)/2,p;
double maxn=0;
for(int i=L;i<=min(mid,R);i++){
if(sq[mid-i]+sum[i]>maxn)maxn=sq[mid-i]+sum[i],p=i;
}
// cout<<mid<<":"<<p<<" "<<maxn<<"\n";
f[mid]=max(f[mid],maxn);
deal(l,mid-1,L,p),deal(mid+1,r,p,R);
return ;
}
signed main(){
n=rd();
for(int i=1;i<=n;i++)sum[i]=rd(),sq[i]=sqrt(i),f[i]=0;
deal(1,n,1,n);
for(int i=1;i<=n/2;i++)swap(sum[i],sum[n-i+1]),swap(f[i],f[n-i+1]);
deal(1,n,1,n);
for(int i=n;i>=1;i--)printf("%d\n",(int)(ceil(f[i])-sum[i]));
return 0;
}