首页 > 代码库 > POJ3273 MonthlyExpense 【裸二分但易错】
POJ3273 MonthlyExpense 【裸二分但易错】
详见blog.csdn.net/lyy289065406/article/details/6648554,也就一简单的很裸的二分。。。
以前看到一句话,90%的程序员会写错二分程序,果不其然,虽然前面二分都写对了,但这个确实卡了一下,还好去洗个澡回来就想出来了,哇哈哈哈
这个要注意,在L<R-1的时候就应该终止二分循环,然后手动选择答案(也就是说有时候二分最后一步需要自己手动选择答案)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int MAXN=155555; int n,m; int day[MAXN]; bool judge(int money) { int sum=0; int group=0; for(int i=1;i<=n;i++) { sum+=day[i]; if(sum>money) { sum=day[i]; group++; } } group++; return group>m; } int main() { #ifndef ONLINE_JUDGE //freopen("/home/test/in.txt","r",stdin); //freopen("/home/test/list.txt","w",stdout); #endif while(scanf("%d%d",&n,&m)!=EOF) { memset(day,0,sizeof(day)); int sum=0; int daymax=0; for(int i=1;i<=n;i++) { scanf("%d",&day[i]); sum+=day[i]; daymax=max(day[i],daymax); } int L=daymax; int R=sum; int mid=(L+R)>>1; //cout<<sum<<endl; while(L<R-1) { if(judge(mid)) { L=mid+1; } else { R=mid; } mid=(L+R)>>1; } if(judge(mid)) mid++; printf("%d\n",mid); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。