POJ 1505(二分+贪心)

题意：给一些书，这些书有不同的页数，让把这些书分成k份，必须是连续的，问这些份中页数和的最大值最小是多少。

解题思路：知道了页数和的范围，而且书都是连续的，要找到页数和最大值的最小值可以直接二分答案。。

AC:

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;

const int MAXM = 505;
int m,k;
int book[MAXM];
bool vis[MAXM];

int divide(int x)
{
	int sum=0,cnt=1;
	memset(vis,false,sizeof(vis));
	for(int i=m;i>=1;i--)
	{
		sum+=book[i];
		if(sum>x)
		{
			cnt++;
			sum=book[i];
			vis[i]=true;
		}
	}
	return cnt;
}

void print()
{
	cout<<book[1];
	for(int i=2;i<=m;i++)
	{
		if(vis[i-1]) cout<<" /";
		cout<<' '<<book[i];
	}
	cout<<endl;
}

int main()
{	
	int cas;
	cin>>cas;
	while(cas--)
	{
		cin>>m>>k;
		int l=0,r=0,mid=0;;
		for(int i=1;i<=m;i++)
		{
			cin>>book[i];
			r+=book[i];
			if(l<book[i]) l=book[i];
		}
		while(l<r)	//二分搜索最大值中的最小值（参见刘汝佳《算法竞赛入门经典》P151）
		{
			mid=(l+r)>>1;
			if(divide(mid)<=k) r=mid;	//这里不能是r=mid-1，原因可参见《算法竞赛入门经典》
			else l=mid+1;
		}
		int cnt=divide(r);
		for(int i=1;i<=m && cnt<k;i++)	//可能分得不足k次，那么就把前面的每一本书分给一个人超(题目要求)
		{
			if(!vis[i])
			{
				vis[i]=true;
				cnt++;
			}
		}
		print();
	}
	return 0;
}