题目描述

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

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

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

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

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

第一段差值为 2 ，第 2 段差值为 2 ，第 3 段差值为 5 ，差值的最小值为 2 。

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

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

数据范围

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

输入格式

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

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

输出格式

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

样例

6 3
1 3 5 7 9 13

2

问题分析

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

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 的，说明分段失败。因为前面的分段是采用节约原则，差值刚刚够 diff 就算，把数字留给后面的段，如果只要少 1 个数字，都会导致某些段的差比 diff 更小。差值比 diff 小，那意味着差的最小值就不是 diff 了。所以，按照这个模式来分段分不出 m 段就是分段失败。换句话说，是没有办法做到每一段的最小值控制在 diff 的情况下分出 m 段数字。

但是假如分出来的段数大于 m ,说明分段还是成功的。因为我们只需要把 m 段以后的所有数字都归到第 m 段即可。之前第 m 段的差就比 diff 大，让 i 指针右移，只会让差更大，所以第 m 段的差还是会比 diff 大，所以，还是能保证每一段的差都能大于等于 diff ，分段成功。

如果按照 diff 作为最小差来分段是分成功的，diff-1 作为最大差来分段仍然是成功的，分段的方法压根就不需要改变，之前的最大差大于等于 diff ，那自然就大于 diff-1；反过来说，如果用 diff 作为最小差来分段是失败的，就说明无论怎么分，某些段的差就是比 diff 更小，那么用 diff+1 作为最小差来分段，肯定也是失败的。某些段的差比 diff 小，自然也比 diff+1 小嘛。

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

完成程序

#include<bits/stdc++.h>
using namespace std;
int x[100002],n,m;
bool check(int diff)
{
	int cnt=0,p=x[1]; //把第一个数字选 x[1] 第一段，p 用来记录当前这一段数字最开始那个 
	for(int i=2;i<=n;i++)
	{
		if(填空(1)) //x[i] 与 p 的差超过了diff ，x[i] 分入这一段之后，这一段的最小值大于等于 diff（如果每一段的最小值都大于等于 diff，那么可以理解为所有段的最小值为 diff） 
		{
			cnt++; // 增加一段
			p = 填空(2);  //记录新的一段的最小值，新的一段的起点是什么呢？
		}
	}

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

}
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(填空(4))
	{
		mid=填空(5);
		if(check(mid)) //用 diff=mid 去分段是可行的，在下半区继续搜索
			填空(6);
		else  //用 diff=mid 去分段是不可行的，在上半区继续搜索
			填空(7);
	}
	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) }}