题目描述

对于给定的一个长度为 N 的正整数数列 a[1..N]，内容本身已经有序，数列为递增序列。现要往数列中插入 M 个数，要求插入数字之后数列依然保持递增形态，并且要求相邻数项之间差值的最大值的最小值。

关于相邻数项查找的最大值，下面有几个例子：

一数列 {11,24,67,92,97} 要插入 3 个数字。

如果插入数字 17, 45, 69 ，新数列为：{11,17,24,45,67,69,79,97} ,则新数列的相邻数项差为：{6,7,21,22,2,10,18} ，最大值为 22 。

如果插入数字 46, 80, 94 ，新数列为：{11,24,46,67,80,92,94,97} ,则新数列的相邻数项差为：{13,23,21,13,12,2,3}，最大值为 23 。

如果插入 39, 54, 80，如果新数列为：{11,24,39,54,67,80,92,97} ,则新数列相邻项的差为 {13,15,15,13,13,12,2}，最大值为 15 。

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

所以在数列 {11,24,67,92,97} 中插入 3 个数字，新数列相邻数项的差的最大值的最小值为 15 （也就是说差的最大值不小于 15 ）。

数据范围

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

输入格式

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

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

输出格式

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

样例

5 3
11 24 67 92 97

15

问题分析

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

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

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

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

原数列是递增的，插入数字之后仍然保持递增，那意味着我们在 $a_i$ 和 $a_{i+1}$ 之间插入数字 t，必须满足 $a_i$ <= t <= $a_{i+1}$ 。我们要保证新数列的差的最小值为 diff ，就要在原数列的差大于 diff 的那些位置插入数字。例如，原数列有两个相邻的数项是 1 和 101 ，要实现新数列的差的最大值为 10 ，就只能在 1 和 101 之间插入一系列的数字（插入数字之后 1 和 101 就不是相邻项了）。插值的时候我们选用节约原则，尽可能插入少一些数字。必须先插入 11，使得 11 和 1 的差达到 10 ，然后再插入 21 ，使得 21 和 11 的差达到 10 ，然后插入 31,41,....,91。这个事情可以用整除运算来化简，假如 $a_i$ - $a_{i-1}$ 是 diff 的整数倍，那就插入 ($a_i$ - $a_{i-1}$)/diff - 1 个数，否则，就插入 ($a_i$ - $a_{i-1}$)/diff 个数。

为了实现相邻项目的差的最大值尽可能小，我们就需要在相隔比较远的那些数字之间插入数字。两个数字的大小差异越大，要插入的数字就越多，这样才能使得从全局来看，差的最大值就会没那么大，而那些原本就差距很小的位置，就可以少插入甚至不插入数字。

对于每一个要检验的 diff ，检验的方法就是看最终需要插入多少个数字。如果最终算出来要插入 cnt=m 个数字，明显就是可行。如果插入小于 m 个数，也是可行。因为可以随便找些空位来插入数字，凑够 m 个数就可以了，后面随意插入的数字只会让数列相邻项的差进一步变小，维持最大值不超过 diff 的情况，所以可行。而如果要插入超过 m 个数才能使得新数列的差的最大值为 diff ，意味着只要少插一些数，新数列的某些数项之间的差就会不止 diff ，也就是说 diff 并不是所有相邻数项的差的最大值了，换言之，无法做到插入 m 个数就能使得新数列的相邻数项的差的最大值为 diff。

如果按照 diff 作为差的最大值来插值是成功的，那么以 diff+1 作为差的最大值来插值仍会是成功的，插入的数字压根就不需要改变，之前方案的新数列既然满足于相邻项的差小于等于 diff ，那自然就会小于等于 diff+1；反过来说，如果用 diff 作为最大差来插值是失败的，那么用 diff-1 作为最小差来插值肯定也是失败的。因为只插入 m 个数的时候，某些相邻数项的差是大于 diff 的，那自然也就大于 diff-1 ，所以还是无法做到插入 m 个数就使得相邻数项的差的最大值为 diff-1 。

综上所述，diff 的大小和插值是否成功是存在单调性的。小的 diff 是无法完成的任务，但是随着 diff 增大到某个值，插值任务就可以成功了，而且之后更大的 diff 都会成功。本题问的，就是能插值成功的最小的那个 diff ，这是左边界查询。

完成程序

#include<bits/stdc++.h>
using namespace std;
int x[100001],n,m;
bool check(int diff) //检查能否以 diff 作为新数列的相邻项之差的最小值
{
	int cnt=0;
	for(int i=填空(1);i<=n;i++)
	{
		if(填空(2)) //x[i] 与 x[i-1] 的差超过了diff ，需要在 x[i-1] 和 x[i] 之间插入若干个数
		{
			if((x[i]-x[i-1])%diff==0)
				cnt += 填空(3);
			else
				cnt += 填空(4); 
		}
	}

	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) }}