首页 > 代码库 > codeforces 460C - Present 二分加模拟
codeforces 460C - Present 二分加模拟
代码有详细解释,二分模拟寻找结果,贪心选择从哪开始浇花,原则就是遇到需要浇花的就浇,至于w可以用线段树来维护线段,但也可以用一个数组标记一下,二分总是有很多问题啊,所以写很多输出用来调试,jiong
/************************************************************************* > File Name: 460c.cpp > Author: yang > Mail:826123027@qq.com > Created Time: 2014年08月22日 星期五 11:17:43 ************************************************************************/ #include<iostream> using namespace std; #include<memory.h> #include<stdio.h> #define N 100005 int a[N]; int main(){ int n,m,w,memory[N],b[N]; while(cin>>n>>m>>w){ int l=0x7FFFFFFF,r=0; for(int i=0;i<n;i++){ cin>>a[i]; if(a[i]<l) l=a[i]; if(a[i]>r) r=a[i]; } r+=m;//最长的高度 while(l<=r){//这里一开始没有=号,wa了一次 int tempm=m; int mid=(l+r)>>1; for(int i=0;i<n;i++){ b[i]=mid-a[i];//b数组用来记录每朵花需要的天数 if(b[i]<=0) b[i]=0; } memset(memory,0,sizeof(memory));//记住什么时候结束w长度的浇花 int index=0,x=0;//x表示每朵花在因为前面浇花的的影响,也应该得到的浇花天数,例如前面i花浇x天,w为3,那么i+1,i+2的花也得到了x天的浇花 for(int i=0;i<n;i++){ x+=memory[i]; if((b[i]-x)>0){ b[i]-=x; tempm-=b[i]; if(tempm<0){ break; } x+=b[i];//x累计能从前面浇花时得到浇花天数 memory[i+w]-=b[i];//长度活了w之后将的得到的浇花天数还回去 } } if(tempm>=0) l=mid+1; else r=mid-1; } printf("%d\n",l-1); } }
codeforces 460C - Present 二分加模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。