「BZOJ2216」[POI2011] Lightning Conductor

2014年11月29日3,8136

Description

已知一个长度为n的序列a1,a2,…,an。
对于每个1<=i<=n,找到最小的非负整数p满足 对于任意的j, aj < = ai + p – sqrt(abs(i-j))

Input

第一行n,(1<=n<=500000)
下面每行一个整数,其中第i行是ai。(0<=ai<=1000000000)

Output

n行,第i行表示对于i,得到的p

Sample Input

6
5
3
2
4
2
4

Sample Output

2
3
5
3
5
4

题解

倒腾一下式子得出f[i]=max{a[j]+sqrt(abs(i-j))}-a[i]

为了把绝对值去掉就正反各做一次取最大值

这个式子显然是满足决策单调的

ydc神犇好像写过题解

http://ydcydcy1.blog.163.com/blog/static/2160890402013315391435/

 

 

说点什么

提醒
avatar
广大圆明

黄学长,您好,第32line的r=mid-1不应该是r=mid吗?蒟蒻,求轻喷