题目描述

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

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

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

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

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

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

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

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

数据范围

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

输入格式

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

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

输出格式

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

样例

5 3
4 2 4 5 1

4

问题分析

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

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

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

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

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

如果按照这个思路刚好分出了 m 段，那很好理解，说明可以按照 s 作为和的最小值来完成分段。如果分出来的段数是小于 m 段怎么理解呢？那自然就是不 OK 啊。因为分段采用节约模式，我们对任何一个分段哪怕少分 1 个数字，该段的和都达不到 s ，那就说明了 s 不是所有段的和的最小值了，也就意味着无法按照和最小值为 s 完成分组。

但是，如果分出来的段数大于 m 段呢？其实这时候是可以的。你可以把第 m 段之后的数字全部归到第 m 段，这样仍然能满足每一段的和都达到或者超过了 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,MIN;
bool check(long long s) //测试最小和为 s 是否可行
{
	int cnt=0,i; //只有一段数字的和达到 s ，才算一段。所以一开始 cnt 为 0
	long long sum=0;
	for(i=1;i<=n;i++)
	{
		sum += a[i]; //把 a[i] 分到当前的这个段落
		if(填空(1)) // 这一段的和达到了 s ，
		{
			填空(2); //之前的数字构成了一段
			填空(3); // 复位累加变量
		}
	}
	
	return 填空(4);  // 根据段数判断是否分段成功
}
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];
		MIN = max(MIN,a[i]);
	}

	long long low=1,high=s,mid; //每一段的和的最小值可以从 1 开始，也可以从 a[i] 的最小值开始

	while(low+1<high)
	{
		mid = (high+low)/2;
		if(check(mid)) // 按照 s=mid 去分段可以的
			填空(5); //缩小枚举的区域，在下半区找左边界
		else // 按照 s=mid 去分段是不行的
			填空(6);  //缩小枚举的区域，在上半区找左边界
	}
	if(check(填空(7) ))
		cout<<填空(7);
	else
		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) }}