【bzoj2216】[Poi2011]Lightning Conductor

2014年11月29日3,1295

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/

 

 

  • 广大圆明2016年3月6日 下午1:54 回复

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

    #1  
    • hzwer2016年3月6日 下午5:37 回复

      每个人有不同的二分写法吧

      #11
      • 广大圆明2016年3月7日 下午9:26 回复

        我发现把=号去掉,然后改成r=mid根本过不了啊,跪求解释

        #12
        • hzwer2016年3月8日 下午8:01 回复

          想一想,为什么?

          #13
          • 广大圆明2016年3月16日 下午5:19

            我问了好多人他们说不知道,如果判断了是不是根本不存在解,还是WA,所以我就改成了黄学长这种写法了,他们好像都这样写2分,然后我就这样写了,目前还没有错过。。。

            #14