题目描述

对于给定的一个长度为 N 的正整数数列 a[1..N]，现要将其分成 M ( M ≤ N )段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：例如一数列 {4,2,4,5,1} 要分成 3 段。

将其如下分段：[4 2] [4 5] [1]

第一段和为 6，第 2 段和为 9 ，第 3 段和为 1 ，和最大值为 9 。

将其如下分段：[4] [2 4] [5 1]

第一段和为 4 ，第 2 段和为 6 ，第 3 段和为 6 ，和最大值为 6 。

并且无论如何分段，最大值不会小于 6 。

所以可以得到要将数列 {4,2,4,5,1} 要分成 3 段，每段和的最大值最小为 6 。

数据范围

对于 100% 的数据，1≤ N≤ $10^6$ , M ≤ N , $a_i$ ≤ $10^8$

输入格式

第 1 行包含两个正整数 N , M 。

第 2 行包含 N 个空格隔开的非负整数 $a_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

样例

5 3
4 2 4 5 1

6

问题分析

本题符合二分算法的所有特征：

1. 结果不容易直接算出来，但是，可以验证一个数字是否可行，而且很容易验证；

2. 如果能枚举所有数字，就能知道题目的答案，题目问的内容就是所有可行方案中的最小值

3. 我们称每一段的最大值为 sum, 这个 sum 和 方案是否可行之间具有单调性。关于这一点，下面详细论述。

在分段的时候，要检验和的最大值为 s 分出 m 段, 只需要保证每一段的和都小于等于 s，然后比较最终分段的数量，这是检验思想的大方向。具体来说，就是分段的时候，在保证每一段和不超过 s 的情况下，把尽可能多的数字分到这一段（i 坐标尽量右移），看能否分出 m 段，就能检验出和的最大值为 s 的可行与否。

如果按照这个思路刚好分出了 m 段，那很好理解，说明可以按照 s 作为和的最大值来完成分段。如果分出来的段数是大于 m 段怎么理解呢？那自然就是不 OK 啊。我们试想一下，刚好分出 m 段的时候，还剩下一些数字，而前面的小组其实已经是尽力去接纳尽可能多的数字了，他们没法接纳更多，如果多接纳哪怕 1 个数字，某些段的和就会超过 s，超过了 s ，就说明 s 不是所有段的和的最大值了，也就意味着无法按照和的最大值为 s 完成分组。

但是，如果分出来的小组小于 m 段呢？其实这时候是可以的。你可以可以对前面的一些小组做拆分，它们原本的和就不够 s ，一个小组拆成 2 个甚至更多个，每个拆出来的小组的和都不会超出 s 。所以，分出来的段数小于 m 是 OK 的。

上面的思路有贪心算法的思维模式，我们采用这个思路，按照和不超过 s 去分段，是可以分出 m 段的，我们可以想象按照和不少于 s+1 去分段，肯定也是可以分出 M 段的，之前按照 s 分段的方法压根都不需要变化，反正每一段的和不超过 s，也自然不会超过 s+1 。

反过来说，假设按照和不超过 s （可以等于 s ）去分段，分不出 m 段，那么，我们按照和少于 s-1 去分段，肯定也分不出 m 段。这就是单调性。

我们可以想象，s 很小的时候，是分不成功的，但是这个 s 到了某个数字之后，就可以分成功了，而且之后更大的 s 也能分成功。我们找出的是这个问题的左边界，第一个，也是最小的那个可以分成功的 s，其实，这就是二分法里面的左边界查询问题。

完成程序

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int n,m,MAX;
bool check(long long s) //测试最大和为 s 是否可行
{
	int cnt=1,i; //一开始就有开始第一个段落
	long long sum=a[1];
	for(i=2;i<=n;i++)
	{
		if( 填空(1) ) //加上这一个 a[i] 也不超过 s
			sum += a[i]; //把 a[i] 继续分到当前的这个段落
		else
		{
			填空(2); //新增一个段落
			填空(3); // 这个段落里面的第一个数是 a[i]
		}
	}
	
	return cnt<=m;
	/*上面这句话相当于下面这几行：
	if(cnt<=m) return true;
	else return false;
	*/
}
int main()
{
	scanf("%d%d",&n,&m);
	int i;
	long long s=0; 
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		s += a[i];
		MAX = max(MAX,a[i]);
	}

	long long low=MAX,high=s,mid; //每一段的和的最小值不能小于 a[i] 的最大值，否则那些大的数字就无法成功分入段，即便只有它 1 个数字都超出了最大和。

	while(填空(4))
	{
		mid = 填空(5);
		if(check(mid)) // 按照最大和 s=mid 去分段是ok的
			填空(6); //缩小枚举的区域，在上半区找左边界
		else // 按照 s=mid 去分段是不行的
			填空(7);  //缩小枚举的区域，在下半区找左边界
	}
	cout<<填空(8);

	return 0;
}

填空(1) :{{ input(1) }}

填空(2) :{{ input(2) }}

填空(3) :{{ input(3) }}

填空(4) :{{ input(4) }}

填空(5) :{{ input(5) }}

填空(6) :{{ input(6) }}

填空(7) :{{ input(7) }}

填空(8) :{{ input(8) }}