本文主要是介绍Landscape Improved Gym - 100851L，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/gym/100851/attachments
又是这种“金字塔型”的题目 就是题目要求构造形如1 2 3 4 5 4 3 2 1这样的序列 或者一些相关的操作
这样的题不好直接维护 对每个位置的数pos[i]都减去其下标i和(n-i+1) 构成两个新序列 这样就等于把这份序列转了45度 很容易就可以用线段树搞一搞
这个题也是 对每个位置i 二分一个峰值 然后判断是否符合条件 对于当前二分的这个值 找出左边的一个大于等于他的数 位置记为pl 同理右边的记为pr [pl+1,i-1]和[i+1,pr-1]这两个区间内有多少位置小于二分值 都要补齐 然后算一下花费来判断即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;struct node
{ll lsum,lmaxx;ll rsum,rmaxx;
};node tree[4*maxn];
ll s;
ll ary[maxn],lef[maxn],rgt[maxn];
int n;void pushup(int cur)
{tree[cur].lsum=tree[2*cur].lsum+tree[2*cur+1].lsum;tree[cur].lmaxx=max(tree[2*cur].lmaxx,tree[2*cur+1].lmaxx);tree[cur].rsum=tree[2*cur].rsum+tree[2*cur+1].rsum;tree[cur].rmaxx=max(tree[2*cur].rmaxx,tree[2*cur+1].rmaxx);
}void build(int l,int r,int cur)
{int m;if(l==r){tree[cur].lsum=tree[cur].lmaxx=lef[l];tree[cur].rsum=tree[cur].rmaxx=rgt[l];return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}void queryI(int tp,int &res,int pl,int pr,ll val,int l,int r,int cur)
{ll tmp;int m;if(pl<=l&&r<=pr){if(!tp) tmp=tree[cur].lmaxx;else tmp=tree[cur].rmaxx;if(tmp>=val){if(l==r) res=l;else{m=(l+r)/2;if(!tp){if(pr>m) queryI(tp,res,pl,pr,val,m+1,r,2*cur+1);if(res!=-1) return;if(pl<=m) queryI(tp,res,pl,pr,val,l,m,2*cur);}else{if(pl<=m) queryI(tp,res,pl,pr,val,l,m,2*cur);if(res!=-1) return;if(pr>m) queryI(tp,res,pl,pr,val,m+1,r,2*cur+1);}}}return;}m=(l+r)/2;if(!tp){if(pr>m) queryI(tp,res,pl,pr,val,m+1,r,2*cur+1);if(res!=-1) return;if(pl<=m) queryI(tp,res,pl,pr,val,l,m,2*cur);}else{if(pl<=m) queryI(tp,res,pl,pr,val,l,m,2*cur);if(res!=-1) return;if(pr>m) queryI(tp,res,pl,pr,val,m+1,r,2*cur+1);}
}ll queryII(int tp,int pl,int pr,int l,int r,int cur)
{ll res;int m;if(pl<=l&&r<=pr){if(!tp) return tree[cur].lsum;else return tree[cur].rsum;}res=0,m=(l+r)/2;if(pl<=m) res+=queryII(tp,pl,pr,l,m,2*cur);if(pr>m) res+=queryII(tp,pl,pr,m+1,r,2*cur+1);return res;
}bool judge(int pos,ll add)
{ll lefsum,rgtsum,len;int pl,pr;pl=-1,pr=-1;if(1<=pos-1) queryI(0,pl,1,pos-1,lef[pos]+add,1,n,1);if(pos+1<=n) queryI(1,pr,pos+1,n,rgt[pos]+add,1,n,1);//printf("*%d %d*\n",pl,pr);if(pl==-1||pr==-1) return 0;if(pl+1<=pos-1){len=(pos-1)-(pl+1)+1;lefsum=(lef[pos]+add)*len-queryII(0,pl+1,pos-1,1,n,1);}else lefsum=0;if(pos+1<=pr-1){len=(pr-1)-(pos+1)+1;rgtsum=(rgt[pos]+add)*len-queryII(1,pos+1,pr-1,1,n,1);}else rgtsum=0;if(lefsum+rgtsum+add<=s) return 1;else return 0;
}int main()
{ll l,r,m,ans,val;int i;freopen("landscape.in","r",stdin);freopen("landscape.out","w",stdout);scanf("%d%lld",&n,&s);for(i=1;i<=n;i++){scanf("%lld",&ary[i]);lef[i]=ary[i]-i+1;rgt[i]=ary[i]-(n-i+1)+1;}build(1,n,1);ans=0;for(i=1;i<=n;i++){//printf("***%d***\n",i);l=0,r=2e9,val=0;while(l<=r){m=(l+r)/2;if(judge(i,m)) val=m,l=m+1;else r=m-1;}ans=max(ans,ary[i]+val);}printf("%lld\n",ans);return 0;
}
这篇关于Landscape Improved Gym - 100851L的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
