本文主要是介绍Bear and Blocks CodeForces - 574D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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;
}
这篇关于Bear and Blocks CodeForces - 574D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
