题目描述

对于给定的一个长度为 N 的正整数数列 a[1..N]，内容本身已经有序，数列为非下降序列。现要将其分成 M ( M ≤ N )段，并要求每段连续，且每段数字差值的最大值最小。

关于差值最大值最小：例如一数列 {1 3 5 7 9 13} 要分成 3 段。

将其如下分段：[1 3] [5 7] [9 13]

第一段差值为 2，第 2 段差值为 2 ，第 3 段值差为 4 ，差值的最大值为 4 。

将其如下分段：[1] [3 5 7] [9 13]

第一段差值为 0 ，第 2 段差值为 4 ，第 3 段差值为 4 ，差值的最大值为 4 。

将其如下分段：[1 3] [5 7 9] [13]

第一段差值为 2 ，第 2 段差值为 4 ，第 3 段差值为 0 ，差值的最大值为 4 。

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

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

数据范围

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

输入格式

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

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

输出格式

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

样例

6 3
1 3 5 7 9 13

4

问题分析

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

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

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

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

题目中有两个关键的信息，数列是递增的，而且要连续分段。所以，假设从 $a_j$ 到 $a_i$ 是完整的一段，那么段内最大的数字是 $a_i$，最小的数字是 $a_j$，这一段的差就是 $a_i-a_j$ ，我们只要把 i 坐标右移，把 $a_i$ 后面更多的数字吸纳到这一段，那么这一段的差就会变大，反过来说，如果我们把 i 坐标左移，就可以让这一段的差变小。

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

用上述方法分出来的分段数刚好等于 m , 我们自然知道是分段成功了。假设分出来的段数是大于 m 的，说明分段失败。因为前面的分段都已经是尽可能多的把数字分到段落，处于临界状态，只要再分多哪怕 1 个数字，某些段的差就会超过 diff , 超过了 diff 就意味着实际的最大差值是不止 diff 了。换句话说，是没有办法做到每一段的最大值控制在 diff 的情况下分出 m 段数字。

但是假如分出来的段数小于 m ,说明分段还是成功的。因为我们只需要把前面段进行拆分，1 个段拆分成 2 段或者更多的段，之前的差就本来就小于 diff ，拆分之后只会更小。所以，这些新段的差依然不会超过 diff ，所以，这按照上面的方法分出来的段数少于 m 是属于分段成功。

如果按照 diff 作为最大差来分段是分成功的，diff+1 作为最大差来分段仍然是成功的，分段的方法压根就不需要改变，之前的最大差小于等于 diff ，那自然就小于 diff+1；反过来说，如果用 diff 作为最大差来分段是失败的，那么用 diff-1 作为最大差来分段，肯定也是失败的。用更小的 diff 来分段只会分出更多的段落。段落少了可以拆分，段落多了没办法挽救，就是失败。

综上所述，diff 的大小和分段是否成功是存在单调性的。小的 diff 是分不成功的，随着 diff 增大，到了某个大小的时候，分段就成功了，而且之后更大的 diff 都成功。本题问的，就是能分成功的最小的那个 diff ，这是左边界查询。

完成程序

#include<bits/stdc++.h>
using namespace std;
int x[100001],n,m;
bool check(int diff)
{
	int cnt=1,p=x[1]; //第一个数字一定选 x[1]，p 用来记录当前这一段数字最开始那个 
	for(int i=2;i<=n;i++)
	{
		if(填空(1)) //x[i] 与 p 的差超过了diff ，x[i] 不能分入这一段，要新开一段 
		{
			填空(2); // 增加一段
			填空(3);  //记录新的一段的最小值
		}
	}

	return 填空(4); //根据分出来的段数判断分段是否成功

}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);
	
	int low=1,high=x[n],mid; //设定初始搜索范围
	
	while(low+1<high)
	{
		mid=(low+high)/2;
		if(check(mid)) //用 diff=mid 去分段是可行的，在上半区继续搜索
			填空(5);
		else  //用 diff=mid 去分段是不可行的，在下半区继续搜索
			填空(6);
	}
	if(check(填空(7)))
		printf("%d",填空(7));
	else
		printf("%d",填空(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) }}