最大连续和的最小值.txt

ACM资料大集合

//最大连续和的最小值 PKU 3273 Monthly Expense 二分法
/*
输入:
30 5
2100 7200 1150 7400 6600
3400 2230 2340 3800 4105
1102 1234 7983 1420 5430
5200 2321 3231 5560 2125
1827 2819 2010 8472 7421
9882 1990 2901 4839 7620

输出：
27231

输入：
8 3
1 2 3 4 5 6 7 8

输出：
15
*/


#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

#define DUIMAX 100005
#define MAX 99999999
long weight[DUIMAX];

int caldui(int num,int max)
{	//限制一堆的最大数量不能超过max时，求得的堆数
	int sum=0,i,dui=0;
	for(i=1;i<=num;i++)
	{
		if(sum+weight[i]<=max) 
		{
			sum+=weight[i];
		}
		else
		{
			sum=0;
			dui++;
			i--;
		}
	}
	return dui+1;
}


int cal(int num,int dui)
{
	long minliang=0,maxliang=0,liang,temp,i;
	for(i=1;i<=num;i++)
	{	//对minliang,maxliang初始化,minliang为最大一个石头的重量，maxliang是石头重量之和
		if(minliang<weight[i]) minliang=weight[i];
		maxliang+=weight[i];
	}
	liang=(minliang+maxliang)/2;
	temp=caldui(num,liang);
	while(minliang<maxliang)//注意这里，不是<=
	{
		if(temp==dui)
		{
			maxliang=liang-1;//注意这里,不是maxliang=liang
		}
		else if(temp<dui) 
			maxliang=liang-1;
		else
			minliang=liang+1;
		liang=(maxliang+minliang)/2;//注意这里，不是liang=(maxliang+minliang+1)/2
		temp=caldui(num,liang);
	}
	return liang;
}

int main()
{
	long num,dui,i;
	scanf("%ld%ld",&num,&dui);
	for(i=1;i<=num;i++)
		scanf("%ld",&weight[i]);
	cout<<cal(num,dui)<<endl;
	return 0;
}