题目描述

对于给定的一个长度为 N 的正整数数列 a[1..N]，内容本身已经有序，数列为非下降序列。现要从中选出 M 个数构成一个新的数列，不改变它们在原数列中的顺序，要求新数列数项之间差值的最小值的最大值。

例如一数列 {11,24,43,52,67,81,92,97} 要从中选出 4 个数字构成新的数列。

如果新数列为：{11,24,67,97} ,新数列的差为：{13,43,30} ，最小值为 13 (最小值一定是出现在相邻数项之间，所以，我们只需要关注相邻数项的差即可）。

如果新数列为：{11,43,81,97} ,相邻项的差为：{32,38,16}，最小值为 16 。

如果新数列为：{11,43,67,97} ,相邻项的差为 {32,24,30}，最小值为 24 。

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

所以可以得到要在数列 {11,24,43,52,67,81,92,97} 中选 4 个数字，数项之间的差的最小值最大为 24 （也就是说差的最小值不超过 24 ）。

数据范围

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

输入格式

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

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

输出格式

一个正整数，新数列的相邻项的差的最小值的最大值。

样例

8 4
11 24 43 52 67 81 92 97

24

问题分析

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

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

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

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

原数列是递增的，而且不能改变新数字在新数列中的顺序，所以，新数列也一定是递增的，所以，后项一定比前项大，因此相邻项的差为 $b_i$ - $b_{i-1}$ 。我们希望差的最小值为 diff ，只需要在选数字的时候保证后项比前项大足够多，相邻项的差值大于等于 diff 即可。

具体的选数办法是：原数列的第 1 个数字必定选，作为新数列的第一项 $b_1$，然后只有选择第一个大于等于 $b_1$+diff 的数作为 $b_2$，然后选第一个大于等于 $b_2$+diff 的数字作为 $b_3$.....这样，就可以保证 $b_i$ - $b_{i-1}$ 都大于等于 diff ，也就是说 diff 是新数列相邻项的差的最小值。然后根据最终选出来的数字个数和 m 比较。

如果用这个方法可以刚好选出 m 个数字，那意味着选数成功。假设能只能选出少于 m 个数，说明选数失败。因为选 $b_i$ 的时候是采用了节约模式，我们总是选尽可能小的 $a_j$ 作为 $b_i$，j 的位置已经是尽量左移的，只要 j 下标再往左移动一点点，都会导致某两个 $b_i$ 和 $b_{i-1}$ 的差值不足 diff ，那就意味着 diff 不是所有相邻项的差的最小值了。换句话说，是没有办法做到控制差的最小值为 diff 的前提下选出 m 个数字。

但是能选出超过 m 个数 ,说明还是成功的。我们就设想选完了前面 m 个数之后不在选更多的数就可以了，前面的 m 个数构成的数列是满足差值都大于等于 diff 的，也就是说前面选出来的 m 个数彼此之间的差值都大于等于 diff ,diff 是这 m 个数的差值的最小值。

如果按照 diff 作为差的最小值来选数是成功的，diff-1 作为差的最小值来选数仍然是成功的，选的数字压根就不需要改变，之前选的 m 个数的差都大于等于 diff ，那自然就大于 diff-1；反过来说，如果用 diff 作为最小差来选数是失败的，那么用 diff+1 作为最小差来选数肯定也是失败的。因为以 diff 作为差的最小值来选数选不出 m 个数的，用更大的 diff 来选数只会选出更少的数字，还是选数失败。

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

完成程序

#include<bits/stdc++.h>
using namespace std;
int x[100001],n,m;
bool check(int diff) //检查是否能以 diff 作为差的最小值来选数
{
	int cnt=填空(1),p=填空(2); //第一个数字一定选 x[1]，p 用来记录上一个选去的数字
	for(int i=2;i<=n;i++)
	{
		if(填空(3)) //x[i] 与 p 的差超过了diff ，选 x[i] 可以保证和上一个选的数字的差大于等于 diff
		{
			cnt++; // 又成功选多了一个数字
			p=填空(4);  //刷新 p
		}
	}

	return 填空(5); //根据选出来的数字个数判断是否成功

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

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

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