首页 > 代码库 > Codeforces Round #262 (Div. 2)C(二分答案，延迟标记)
Codeforces Round #262 (Div. 2)C(二分答案，延迟标记)
这是最大化最小值的一类问题，这类问题通常用二分法枚举答案就行了。
二分答案时，先确定答案肯定在哪个区间内。然后二分判断，关键在于怎么判断每次枚举的这个答案行不行。
我是用a[i]数组表示初始时花的高度，b[i]表示要达到当前枚举的答案（即mid的值）需要这朵花再涨多少。这两个数组很好算，关键是一次浇连续的w朵花，如何更新区间（暴力的O（n2）的去更新就超时了）？可以用线段树，但是这道题没有涉及区间查询，就是在一个数组上更新区间，用线段树未免小题大做。那么其实这种更新就用延迟标记的思想（懒操作）就可以O（n）的解决了。具体方法参见这道很裸的题：hdu4970
lazy[]这个标记数组的作用其实就是能记录更新区间到哪里停止.
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long intconst int maxn=110009;int n,m,w,a[maxn],b[maxn],lazy[maxn],ans=0;/*lazy[]这个标记数组的作用其实就是能记录更新区间到哪里停止*/int main(){ //freopen("in6.txt","r",stdin); scanf("%d%d%d",&n,&m,&w); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } int l=1,r=maxn+INF,mid; while(l<=r) { memset(lazy,0,sizeof(lazy)); mid=(r+l)/2; for(int i=1; i<=n; i++) b[i]=max(0,mid-a[i]); int tm=m,x=0; for(int i=1;i<=n;i++)//开始浇水 { x+=lazy[i];//要先看这一步是不是有标记 b[i]-=x;//把前面对影响到当前b[i]的浇水操作浇上 if(b[i]>0)//还大于0，那么就必须要从它开始再来一段浇水了 { tm-=b[i]; if(tm<0) break;//天数限制到了 lazy[i+w]-=b[i]; x+=b[i]; } } if(tm<0) r=mid-1; else { ans=mid; l=mid+1; } } printf("%d\n",ans);}
Codeforces Round #262 (Div. 2)C(二分答案，延迟标记)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。