洛谷OJ - P1182 - 数列分段Section II（二分模板）（多组输入版本）

题目描述

有一个长度为n的数列num，要求将数列分为m段，每段必须连续，我们把每段的

和称为“段和”，那么如何分段才能使最大的 “段和” 最小,求出这个最小值

输入格式

注意：多组输入

每组第一行两个正整数n和m

第二行n个正整数，每个正整数( num[i] )之间空格分隔 （如样例所示）

1<=m<=n<=100000

1<=num[i]<=10000

输出格式

每组输出一个正整数，即最小 “段和”，每组各占一行输出

样例输入

5 3

4 2 4 5 1

样例输出

6

思路分析：

1.首先此题是典型的二分思想，求取最大值中的最小值的问题（不要被绕晕，晕就多读几遍）

2.此题中的check函数可以继续依照前几次的数列分段模式，将l定义为数列中的最大元素，r定义为所有的元素之和，所以最小的“段和”必定处于这两个值之间，然后每次判断取到mid为最小段和时候，所需要的将数列分成的段数和输入的m（也就是我们希望分成几段）相比较

3.如果数量少于等于m，就说明我们的段和太大，取r=mid；否则就是段和太小，取l=mid+1；（整数二分模板的取值问题，可以防止边界问题）最终取到的值必然是最大值中的最小值

代码

#include<iostream>
#include<algorithm>

using namespace std;

int n,m;
int l,r;
int a[100010];

int check(int mid)//check函数过程如果不清楚，建议那张纸推一下，很快就清楚
{
	int cnt=1;
	int sum=0;
	for(int i=0;i<n;i++)
	{
		sum+=a[i];
		
		if(sum>mid)
		{
			cnt++;
			sum=a[i];
		}
	}
	if(cnt<=m) 
	return 1;
	else 
	return 0;
}


int main()
{
	while( cin>>n>>m)
	{

	for(int i=0;i<n;i++) 
	{
	cin>>a[i];
	r+=a[i];
	l=max(a[i],l);
}
    while(l<r)
    {
        int	mid=(l+r)>>1;
    	if(check(mid)) r=mid;
    	else l=mid+1;
	}
	
	cout<<l<<endl;
	l=0;r=0;//多组输入记得归0
}

    return 0;
}