二分法有朴素二分、特殊二分、二分答案。今天这篇说一下二分答案的具体问题和思路。只有答案有序时才可以这么用哦
image.png
image.png
//#389 暴躁的程序猿
//把暴躁的n个程序员安排在m个工位中，根据它们的编号和工位数求他们之间的最大距离
//员工编号 1 2 8 4 9
//员工编号排序1 2 4 8 9
//距离d = 1 ,工位m = 5
//距离d = 2 ,工位m = 3,1 4 8或 1 4 9两种情况
//距离d = 3 ,工位m = 3
//距离d = 4 ,工位m = 2, 1 8, 1 9, 2 8, 2 9, 4 8, 4 9 六种情况
//距离d = 5 ,工位m = 2, 1 8, 1 9, 2 8, 2 9
//距离d = 6 ,工位m = 2, 1 8, 1 9, 2 8, 2 9
//距离d = 7 ,工位m = 2, 1 8, 1 9
//距离d = 8 ,工位m = 2, 1 9
//距离d = 9... ,工位m = 1,就随便找一个人坐
//距离d可以无限大，工位m为1的时候
//假设距离已知，给一个距离，对应一个工位，随距离增大工位数减小
//距离是从1到 最大编号和最小编号的差
//给你m让你求最大的距离d
//不好求这个问题，但是给一个d能算出分配的工位数m
//可以根据d先求出这个m数，再和题目比较。可能会有一堆d满足。
//d的范围 是从1到 最大编号和最小编号的差 ，怎样在这一堆数里挑一个合适的d呢
//即有一堆满足条件的d，找出最后一个满足条件的d
//最后一个1前面的情况属于func(d) > = m,后面的情况属于func(d) < m
//满足条件看成1，不满足看成0
//抽象成一个1111000的问题，找用二分法找一个d,让它恰巧等于m
//如果m比题目给定的小，说明你的距离偏大，应该动右边的指针
//如果和题目相等，也应该动左边的指针，看看后边是否有满足条件的d，如果有的话选后边那个
//如果比题目给的大，说明你的距离偏小，应该动左边的指针
/*二分查找的两种特殊情况的解决方法
0001111 找第一个1
while (l != r) { //(l<r)
int mid = (l + r) / 2;
if (mid == 0) { //
l = mid + 1;
} else {
r = mid;//因为右边的数可能就是第一个1
}
}
1111000 找最后一个1
while (l != r) {
int mid = (l + r + 1) / 2;
//避免为待比较数据个数为偶数(可能刚开始就是偶数，也可能循环到某一次变为偶数，且前一个值满足if条件时。比如后面例子m = 2的 情况) 如1 0出现死循环的情况
if (mid == 1) {
l = mid;
} else {
r = mid - 1;
}
}
*/
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, num[10005], str;
//求一下能安排多少人
int func(int d) {
int s = 1, last = num[0];
//无论d是几，都可以在在num[0]放一个人 last记录上个人的位置是哪
//把每个员工都扫一遍，不需要记录它们的位置
for (int i = 1; i < n; i++) {
if (num[i] - last >= d) {
s++;
last = num[i];
}
}
return s;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) [
cin >> num[i];
tr = max(tr, num[i]);
//最大的程序员的编号
]
sort(num, num + n);
int l = 1, r = tr;//这里把范围给到了最大编号，可能会多比较几次
while (l != r) {
int mid = (l + r + 1) / 2;
int s = func(mid);
if (s >= m) { //已知m，算一个距离
l = mid;
} else {
r = mid -1;
}
}
cout << l << endl;
return 0;
}
为了防止溢出，mid = (l + r) / 2，可替换为mid = l + (r - l) / 2 ，java中可换为mid = (low + high) >>> 1
详细解释见https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
