暴躁的程序员

某公司的程序猿每天都很暴躁，因为他们每个人都认为其他程序猿和自己风格不同，无法一同工作。

当他们的工位的编号距离太近时，他们可能会发生语言甚至肢体冲突，为了尽量避免这种情况发生。现在公司打算重新安排工位，因为有些关系户的工位是固定的，现在只有一部分工位空了出来：

现在有 N 个程序猿需要分配在 M 个工位中，第 i 个工位的编号为 Xi，工位编号各不相同，现在要求距离最近的两个程序猿之间的距离最大，求这个最大距离是多少? Xi 和 Xj 工位之间距离为|Xi −Xj|。

输入：

输入共 M+1行，第一行两个整数 M, N（2 ≤ N ≤ M ≤ 100,000）

接下来 M 行，每行一个数表示剩余的工位的编号。

输出：

输出距离最近的两个程序猿之间的最大距离。

样例：

1
2
3
4
5
6
5 3
1
2
8
4
9
1
3

1.解题思路

image-20211011095943525

  1. 根据每一个二分答案长度num[i]，利用fun()函数进行计算，求出其对应的能够安排的程序员人数
  2. 根据当前能够分的人数s与题目给定需要分配的人数m进行比较，从而调整左右指针
  3. 当左右指针逼近到一定范围时，表示最佳答案已经找到

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<algorithm>
using namespace std;

int n, m, num[100005];

int func(int x) {
    int t = 1, last = num[0];
    for (int i = 1; i < n; ++i) {
        if (num[i] - last >= x) {
            ++t;
            last = num[i];
        }
    }
    return t;
}

int bs() {
    int l = 1, r = num[n - 1] - num[0];
    while (l != r) {
        int mid = (l + r + 1) / 2;
        int s = func(mid); //当假设最大距离为mid时求出的分配程序员数量s
        if (s >= m) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
    }
    sort(num, num + n);
    cout << bs() << endl;
    return 0;
}