首页 > 代码库 > NYOJ 680 摘枇杷

NYOJ 680 摘枇杷

摘枇杷

时间限制:2000 ms  |  内存限制:65535 KB
难度:3
描述

理工学院的枇杷快熟了,ok,大家都懂得。而且大家都知道,学校的枇杷树都是一列一列的。现在小Y同学已经在筹划怎么摘枇杷了。现在我们假设有一列枇杷树,而且每棵枇杷树上枇杷果的数量小Y都已经知道了。

假设现在有n棵枇杷树,小Y可以把这n棵枇杷树分成m组,每组枇杷果的数量是这组内每棵枇杷树上枇杷果数量的和。注意,每组的枇杷树必须是连续的。(每组最少1棵树,最多n棵树)。小Y把枇杷往寝室拿的时候是一组一组拿的,所花费的力气等于这m组中枇杷果最多的那组枇杷果的数量。现在小Y想花尽量少的力气把这些枇杷果拿回寝室。

输入
多组测试数据,以EOF结束(<= 100组)
每组测试数据第一行有两个数n(n <= 1000)和m(1 <=m <= n)
第二行有n个数,分别代表每颗树上枇杷果的数量
输出
输出小Y同学所花费的最小的力气,每个结果占一行。
样例输入
3 2
1 2 3
7 5
1 4 3 1 5 2 4
样例输出
3
5
二分+贪心!
AC码:
#include<stdio.h>
int m,sum,max,n;
int a[1005];
int judge(int x)
{// 该函数功能是判断能否把给定序列划分为每个序列之和不大于x的m个子序列
	int count=0,s=0,i;   // count表示划分线的条数
	// 每次都是从左往右划分,划分线的条数不大于m-1条
	for(i=0;i<n;i++)
	{
		if(a[i]>x)   // 如果有一个元素大于x,则即使在这个数的左边和右边都设有划分线,也不能使划分后的任一序列都不大于x
			return 0;
		if(s+a[i]>x) // 当s+a[i]>x,就不能再将a[i]加上了
		{
			count++; // 需要再多用一条划分
			s=a[i];
			if(count>m-1) // count=m时,表示已经用了m条划分线,将原序列分成了m+1个子序列
				return 0;
		}
		else
			s+=a[i];    // 贪心策略,每使用一条划分线,都分隔尽量多的元素
	}
	return 1;
}
int fun()
{
	int L=max,R=sum,mid;
	while(L<=R)
	{
		mid=(L+R)/2;
		if(judge(mid))
			R=mid-1;
		else
			L=mid+1;
	}
	return L;
}
int main()
{
	int i;
	while(~scanf("%d%d",&n,&m))
	{
		sum=0;
		max=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
			if(max<a[i])
				max=a[i];
		}
		printf("%d\n",fun());
	}
	return 0;
}