P3515 [POI 2011] Lightning Conductor
题目描述
逐渐变化的气候迫使 Byteburg 当局建造一个巨大的避雷针，以保护城市内的所有建筑物。
这些建筑物沿着一条街道排成一行，编号从1 11到n nn。
建筑物和避雷针的高度是非负整数。
Byteburg 的资金有限，只能建造一个避雷针。
而且，正如你所料，避雷针越高，成本越高。
位于建筑物i ii（高度为h i h_ihi）屋顶上的高度为k kk的避雷针可以保护建筑物j jj（高度为h j h_jhj），如果满足以下不等式：
k + h i ≥ h j + ∣ i − j ∣ k + h_i \geq h_j + \sqrt{|i-j|}k+hi≥hj+∣i−j∣
其中∣ i − j ∣ |i - j|∣i−j∣表示i ii和j jj之间的绝对差值。
Byteburg 的市长 Byteasar 请求你的帮助。
编写一个程序，对于每个建筑物i ii，确定如果将避雷针放在建筑物i ii上，能够保护所有建筑物的避雷针的最小高度。
输入格式
标准输入的第一行有一个整数n nn(1 ≤ n ≤ 500 , 000 1 \leq n \leq 500,0001≤n≤500,000)，表示 Byteburg 中的建筑物数量。
接下来的n nn行中的每一行包含一个整数h i h_ihi(0 ≤ h i ≤ 1 , 000 , 000 0 \leq h_i \leq 1,000,0000≤hi≤1,000,000)，表示第i ii个建筑物的高度。
输出格式
你的程序应输出恰好n nn行到标准输出。
第i ii行应给出一个非负整数k i k_iki，表示第i ii个建筑物上避雷针的最小高度。
输入输出样例 #1
输入 #1
6 5 3 2 4 2 4输出 #1
2 3 5 3 5 4说明/提示
题面翻译由 ChatGPT-4o 提供。
思路
动态规划
决策单调性
代码见下
#include<bits/stdc++.h>usingnamespacestd;longlongn;doublea[500005],f[500005],sq[500005];voidabc(longlongl,longlongr,longlongx,longlongy){if(l>=r+1){return;}longlongmid=(l+r)/2,p;doublema=0.00;for(inti=x;i<=min(mid,y);i++){if(a[i]+sq[mid-i]>ma){ma=a[i]+sq[mid-i];p=i;}}if(ma>f[mid]){f[mid]=ma;}abc(l,mid-1,x,p);abc(mid+1,r,p,y);return;}intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];sq[i]=sqrt(i);}abc(1,n,1,n);for(inti=1;i<=n/2;i++){swap(a[i],a[n-i+1]);swap(f[i],f[n-i+1]);}abc(1,n,1,n);for(inti=1;i<=n/2;i++){swap(a[i],a[n-i+1]);swap(f[i],f[n-i+1]);}for(inti=1;i<=n;i++){cout<<(longlong)ceil(f[i])-(longlong)a[i]<<endl;}return0;}
