POI2011 避雷针 Lightning Conductor
题目传送门
题意
气候变化使 \(Byteburg\) 不得不建造一个大型避雷针来保护城市里的所有建筑物。建筑物恰好沿一条街，从 \(1\) 到 \(n\) 编号。
建筑物的高度和避雷针的高度都是非负整数。\(Byteburg\)经费有限，只能建造一个避雷针。而且避雷针越高，价格越贵。
在建筑物 \(i\)（高度为 \(h_i\) ）屋顶放置高为 \(p\) 的避雷针能够保护建筑物 \(j\) 的条件是：
\[h_j \le h_i + p - \sqrt{\lvert i - j \rvert}\]
其中 \(\lvert i - j \rvert\) 表示 \(i\) 和 \(j\) 差的绝对值。
\(Byteburg\) 需要你帮它计算，如果在第\(i\)个建筑物的屋顶放置这样的避雷针的话，避雷针的最小高度是多少。
题解
感觉这题好套路啊…… 显然的一个计算公式:\[ h_i+p=Max \{ h_j+ \sqrt{ | i - j | } \}\] 于是我们就可以分前半部分和后半部分来算，最后取个\(Max\)。考虑前半部分，那么这个决策实际上是单调的。假设\(j<k\)，如果\(h_j+\sqrt{ | i - j | } < h_k + \sqrt { | i - k |}\)，那么\(j\)的决策是永远不会变成最优的。因为\(\sqrt{x}\)的增长速度比\(x\)要慢。于是我们就可以维护单调队列了。正着做一遍，反着做一遍就可以了。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+500;
typedef long long ll;
int n,tail,head;
ll h[N];
double ans[2][N];
struct node {
int l,r,idx;
};
node que[N],nw;
double Calc(int x,int y) {
return (double)h[x]+sqrt(abs(x-y))-h[y];
}
int Check(node x,int i) {
double ans1=Calc(x.idx,x.l),ans2=Calc(i,x.l);
return ans1<ans2;
}
void Solve(int tp) {
head=0,tail=-1;
for(int i=1;i<=n;i++) {
if(head<=tail) {
que[head].l++;
if(que[head].l>que[head].r) ++head;
if(head<=tail) {
ans[tp][i]=Calc(que[head].idx,i);
}
}
if(head>tail||Calc(que[tail].idx,n)<Calc(i,n)) {
while(head<=tail&&Check(que[tail],i)) --tail;
if(head<=tail) {
int L=que[tail].l,R=que[tail].r,Ans=-1;
while(L<R) {
int Mid=(L+R)>>1;
if(Calc(que[tail].idx,Mid)<Calc(i,Mid)) R=Mid-1;
else L=Mid+1;
}
que[tail].r=L-1;
` que[++tail]=(node){L,n,i};
}
else que[++tail]=(node){i,n,i};
}
}
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
Solve(0);
reverse(h+1,h+1+n);
Solve(1);
for(int i=1;i<=n;i++) {
ll ret=ceil(max(ans[0][i],ans[1][n-i+1]));
printf("%lld\n",max(0ll,ret));
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10446032.html
