二分法有樸素二分棉圈、特殊二分吭敢、二分答案。今天這篇說一下二分答案的具體問題和思路缭受。只有答案有序時(shí)才可以這么用哦
image.png
image.png
//#389 暴躁的程序猿
//把暴躁的n個(gè)程序員安排在m個(gè)工位中胁澳，根據(jù)它們的編號(hào)和工位數(shù)求他們之間的最大距離
//員工編號(hào) 1 2 8 4 9
//員工編號(hào)排序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,就隨便找一個(gè)人坐
//距離d可以無限大，工位m為1的時(shí)候
//假設(shè)距離已知米者，給一個(gè)距離韭畸，對(duì)應(yīng)一個(gè)工位，隨距離增大工位數(shù)減小
//距離是從1到 最大編號(hào)和最小編號(hào)的差
//給你m讓你求最大的距離d
//不好求這個(gè)問題蔓搞，但是給一個(gè)d能算出分配的工位數(shù)m
//可以根據(jù)d先求出這個(gè)m數(shù)陆盘，再和題目比較“苊鳎可能會(huì)有一堆d滿足。
//d的范圍 是從1到 最大編號(hào)和最小編號(hào)的差 太防，怎樣在這一堆數(shù)里挑一個(gè)合適的d呢
//即有一堆滿足條件的d妻顶，找出最后一個(gè)滿足條件的d
//最后一個(gè)1前面的情況屬于func(d) > = m,后面的情況屬于func(d) < m
//滿足條件看成1，不滿足看成0
//抽象成一個(gè)1111000的問題蜒车，找用二分法找一個(gè)d,讓它恰巧等于m
//如果m比題目給定的小讳嘱，說明你的距離偏大，應(yīng)該動(dòng)右邊的指針
//如果和題目相等酿愧，也應(yīng)該動(dòng)左邊的指針沥潭，看看后邊是否有滿足條件的d，如果有的話選后邊那個(gè)
//如果比題目給的大嬉挡，說明你的距離偏小钝鸽，應(yīng)該動(dòng)左邊的指針
/*二分查找的兩種特殊情況的解決方法
0001111 找第一個(gè)1
while (l != r) { //(l<r)
int mid = (l + r) / 2;
if (mid == 0) { //
l = mid + 1;
} else {
r = mid;//因?yàn)橛疫叺臄?shù)可能就是第一個(gè)1
}
}
1111000 找最后一個(gè)1
while (l != r) {
int mid = (l + r + 1) / 2;
//避免為待比較數(shù)據(jù)個(gè)數(shù)為偶數(shù)(可能剛開始就是偶數(shù)，也可能循環(huán)到某一次變?yōu)榕紨?shù)庞钢，且前一個(gè)值滿足if條件時(shí)拔恰。比如后面例子m = 2的 情況) 如1 0出現(xiàn)死循環(huán)的情況
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]放一個(gè)人 last記錄上個(gè)人的位置是哪
//把每個(gè)員工都掃一遍基括，不需要記錄它們的位置
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]);
//最大的程序員的編號(hào)
]
sort(num, num + n);
int l = 1, r = tr;//這里把范圍給到了最大編號(hào)颜懊，可能會(huì)多比較幾次
while (l != r) {
int mid = (l + r + 1) / 2;
int s = func(mid);
if (s >= m) { //已知m，算一個(gè)距離
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
詳細(xì)解釋見https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
