[Poi2011]Lightning Conductor题解

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;}