二分查找法变形之二分答案——如何根据答案去求答案

二分法有朴素二分、特殊二分、二分答案。今天这篇说一下二分答案的具体问题和思路。只有答案有序时才可以这么用哦

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/

最后编辑于：2020.11.01 21:48:15