bzoj 2216 [POI2011] Lightning Conductor

bzoj 2216 [POI2011] Lightning Conductor

​​ 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 HINT

Source 可以发现sqrt是一个增量单调递减的函数 绝对值我们可以拆开两边各做一遍

所以如果 存在k< j< i 对于i来说现在有k,j两个决策点 如果k决策点现在已经劣于j 那么以后k都不会优于j了 那么我们每次维护一个单调队列 队列中三个元素维护 我这个最优决策点 对应所能产生的最优决策区域是哪里 然后每次首先保证队首是更新我的最优值 然后每次如何把i添加到队列 我们找到第一个i不能优于整个区域的决策点 然后二分这个决策点再哪里不如i优 那么我们就可以把这个决策点拆成l~mid-1 然后添加新的决策点mid~n即可

#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=500050;struct node{ int p,l,r;}data[N],q[N];double dp1[N],dp2[N];int n,a[N];inline double calc(int j,int i){ return a[j]+sqrt(abs(i-j))-a[i];}inline int find(const node &a,int x){ int l=a.l,r=a.r,p=a.p; while(l<=r){ int mid=l+r>>1; if(calc(p,mid)>calc(x,mid)) l=mid+1;else r=mid-1; }return l;}inline void gao(double *dp){ int h=1,t=0; for (int i=1;i<=n;++i){ ++q[h].l;if(h<=t&&q[h].l>q[h].r) ++h; if(h>t||calc(q[t].p,n)t) q[++t]=(node){i,i,n};else{ int md=find(q[t],i); q[t].r=md-1;q[++t]=(node){i,md,n}; } }dp[i]=calc(q[h].p,i); }}int main(){ freopen("bzoj2216.in","r",stdin); n=read(); for (int i=1;i<=n;++i) a[i]=read();gao(dp1); for (int i=1,j=n;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。