http://codeforces.com/problemset/problem/574/D
最后被拿掉的方块肯定在最底层 对于底层的每一个方块就看它外面包着几层方块 比如1234321 最中间第四个最下面的方块外面有三层 算上自己四层 而左右两边的底层方块就只有三层
关键就是怎么求这个层数 对每个位置i的方块数减去i 看左面最小值 与当前位置作差 就是被破坏的层数 右面同理 这个方法和之前codechef上做的一个主席树很像https://blog.csdn.net/sunyutian1998/article/details/82959992
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int N=0x3f3f3f3f; int lef[4*maxn],rgt[4*maxn]; int ary[maxn],prel[maxn],prer[maxn]; int n; void pushup(int *minn,int cur) { minn[cur]=min(minn[2*cur],minn[2*cur+1]); } void build(int *pre,int *minn,int l,int r,int cur) { int m; if(l==r){ minn[cur]=pre[l]; return; } m=(l+r)/2; build(pre,minn,l,m,2*cur); build(pre,minn,m+1,r,2*cur+1); pushup(minn,cur); } int query(int *minn,int pl,int pr,int l,int r,int cur) { int res,m; if(pl<=l&&r<=pr) return minn[cur]; res=N,m=(l+r)/2; if(pl<=m) res=min(res,query(minn,pl,pr,l,m,2*cur)); if(pr>m) res=min(res,query(minn,pl,pr,m+1,r,2*cur+1)); return res; } int main() { int i,ans,res,minnl,minnr; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&ary[i]); for(i=1;i<=n;i++) prel[i]=ary[i]-i; build(prel,lef,1,n,1); for(i=1;i<=n;i++) prer[i]=ary[i]-(n-i+1); build(prer,rgt,1,n,1); ans=0; for(i=1;i<=n;i++){ if(i>1){ res=query(lef,1,i-1,1,n,1); if(res<prel[i]) minnl=min(i,ary[i]-(prel[i]-res)); else minnl=min(i,ary[i]); } else minnl=1; if(i<n){ res=query(rgt,i+1,n,1,n,1); if(res<prer[i]) minnr=min(n-i+1,ary[i]-(prer[i]-res)); else minnr=min(n-i+1,ary[i]); } else minnr=1; ans=max(ans,min(minnl,minnr)); } printf("%d\n",ans); return 0; }
