首页 > 代码库 > 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;
}