zzuliOJ 1919：分割序列（二分+限制条件判断）

1919: D

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 200   Solved: 49

Submit Status Web Board

Description

晴天想把一个包含n个整数的序列a分成连续的若干段，且和最大的一段的值最小，但他有强迫症，分的段数不能超过m段，然后他就不会分了。。。他想问你这个分出来的和最大的一段的和最小值是多少？

Input

第一行输入一个整数t，代表有t组测试数据。
每组数据第一行为两个整数n,m分别代表序列的长度和最多可分的段数。
接下来一行包含n个整数表示序列。
0<=n<=50000 1<=m<=n，0<=ai<=10000。

Output

输出一个整数表示和最大的一段的最小值。

Sample Input

1

3 2

1 3 5

Sample Output

5

HINT

1 3 5 分成一段可以为1 3 5和为9，分成两段可以为1，3 5或者1 3，5，和最大的一段值分别为8，5，所以答案为5

Source

haut

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
int a[50010];
int sum;
int maxx;
bool judge(int x)
{
	int duan=0;//表示分的段数 
	int he=0;
	for(int i=0;i<n;i++)
	{
		if(he+a[i]>x)//当当前段再加一段长度后超过了x的值，那么新开一段 
		{
			duan++;
			he=a[i];
			if(duan>=m)//当还没有扫完这个序列但是已有的段数已经超过了所规定的段数 
			{
				return false;
			}
		}
		else
		{
			he=he+a[i];//延长该段 
		}	
	}
	return true;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		sum=0;
		maxx=-1;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum=sum+a[i];
			maxx=max(maxx,a[i]);
		}
		int l=maxx,r=sum;//左区间用maxx是因为所分的段里面如果不含该序列的最大值，那么这个段子的和一定大于最大值,右区间为sum是因为不分的时候段子和为sum 
		int mid,ans;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(judge(mid))//看是否能将序列分成符合段数不大于m 且最大和接近mid的段子们 
			{
				ans=mid;
				r=mid-1;//求的最小值 
			}
			else
			{
				l=mid+1;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}