丢瓶盖

二分查找 贪心 陶陶是个贪玩的孩子，他在地上丢了 A 个瓶盖，为了简化问题，我们可以当作这 A 个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出 B 个，使得距离最近的 2 个距离最大，他想知道，最大可以到多少呢？

输入格式

第一行，两个整数，$A,B(2\le B\le A\le 10^5)$。

第二行，A 个整数，分别为这 A 个瓶盖坐标，在 $[1,10^9]$ 范围内。

输出格式

仅一个整数，为所求答案。

样例

5 3
1 2 3 4 5

2

思路

「二分」不是单纯指从有序数组中快速找某个数，这只是「二分」的一个应用。 「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

一般看到所谓的最大值最小化或者最小值最大化，一般都是用二分答案进行运算

考虑可以选无限个瓶盖, 在将位置排完序后, 对于所有可能的答案, 一定存在这两种情况：

• 最大距离：$a[n]-a[1]$ 选取最后一个和当前一个
• 最小距离：$min(a[i]-a[j])(i<j且i,j\in [1,n])$ 所有瓶盖都选, 取最小的两个

也就是答案的上界与下界, 既然已经知道答案的范围和构造规则, 且正推很难, 可以从答案逆推。 即对于任何一个距离, 判断能取到时, 所选瓶盖数量是否和 $B$ 相等。

显然根据题目要求, 最小距离可能是$0$, 最大距离可能是$10^9$, 单纯枚举是会超时的。对于查找操作, 我们学过二分, 且用二分解决过在满足单调性的数组中找到任意一个数的问题。

而二分其实是满足两段性才可以使用, 只要一段满足某个性质，另外一段不满足某个性质，就可以用二分。

证明该题可以使用二分, 满足两段性： 假设当前找到的距离为 $mid$ , 满足该距离的情况下, 最多选 $B_{mid}$ 个瓶盖。

• 对于 距离$l\in [l,mid]$ , 其能选的瓶盖数量最多一定符合$B_l>=B_{mid}$
• 对于 距离$r\in [mid,r]$, 其能选的瓶盖数量最多一定符合$B_r<=B_{mid}$

证明： 对于序列$1,2,3,4,5$。选距离最近的两个距离最大。 距离为$3$时, 最多选择$2$个瓶盖$\{\{1,4\},\{2,5\}\}$; 距离为$2$时, 最多选择$3$个瓶盖$\{\{1,3,5\},\{2,4\}\}$ ; 距离为$4$时, 最多选择$2$个瓶盖$\{1,5\}$; 显然成立。

如何求出给定距离的最多选择瓶盖数：

bool check(int x)
{
	int res = 0, j;
	for(int i = 0; i < n; i++)
	{
		for(j = i + 1; j < n && a[j] - a[i] >= x; j++);
		i = j;
		res++;
	}
	return res >= m;
}
 
//或者
bool check(int x)
{
    int res = 1,last = 0;
    for(int i = 1; i < n; i++)
    {
        if(a[i] - a[last] >= x)
        {
            last = i;
            res++;
        }
    }
    return res >= m;
}

最后套一个二分模板即可。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int  N = 1e5 + 10;
int n,m;
int a[N];
 
bool check(int x)
{
    int res = 1,last = 0;
    for(int i = 1; i < n; i++)
    {
        if(a[i] - a[last] >= x)
        {
            last = i;
            res++;
        }
    }
    return res >= m;
}
 
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    sort(a, a + n);
    int l = -1, r = a[n-1] - a[0] + 1;
    while(l != r - 1)
    {
        int mid = (l + r) >> 1;
        if(check(mid))
            l = mid;
        else r = mid;
    }
    if(l == -1) l = 0;
    cout << l << endl;
    return 0;
}