二分答案总结

分析

二分答案是用二分的方法来搜索边界值。由于数据量巨大，用二分法能够有效降低时间复杂度。

二分答案是由一个判断函数f(x)与二分法构成。其中，判断函数能够根据输入的x，得到相应的值。而二分法根据得到的值，调整l和r的大小。

题目特点

出现：最大的最小，最小的最大等等字眼。

f(x)的确定

此处是单独的，一般简单题都是采用“贪心算法”就能获得。因此，贪心是基础。贪心算法就是靠经验。

二分法

首先却l和r。为了加快速度，l与r直接取数据的上下限，而不是数据范围的最大值。计算mid = (l + r) / 2;

定位临界值：设x 是f()变化处临界值。即f(x) != f(x + 1)。而不是f(x - 1) != f(x)。要看清楚是求x还是求x + 1。即是求变化点的低处还是高处。

二分法都是能锁定到变化点的高处，即x + 1。若是求低处，需要将得到的结果减1，获得x。

例题

数列分段Section II

丢瓶盖

例题分析之，丢瓶盖

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

分析

此题是典型的二分答案题，因为要求：距离最近的最大值，满足为B个。

定义f()：距离最近--能够用f(x)写出。即f(x)表示当距离为x时，最大能有对少个瓶盖。此处用贪心算法能够获得。

确定临界值：要求x尽量的大，直到f(x) = B && f(x + 1) > B。

那么也就知道了，用二分法之后要减1才能够得到x。

直接上代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int A, B;
vector<int> v;

int dv(int l, int r)
{
    if (l == r)
        return l;

    int cnt = 1, mid = (l + r) / 2, s = v[0];

    //此处是f(x) 输入mid， 输出cnt。贪心。
    for (int i = 1; i < A; i++)
    {
        if (v[i] - s >= mid)
        {
            cnt++;
            s = v[i];
        }
    }
    //f(x) end.

    //二分法，即使cnt==B也需要mid + 1,因为要求的是边界，相等时mid不一定是最大值。
    if (cnt >= B) return dv(mid + 1, r); 
    else return dv(l, mid);
}

int main()
{
    cin >> A >> B;
    v.resize(A, 0);

    for (int i = 0; i < A; i++)
        cin >> v[i];

    sort(v.begin(), v.end());

    int l = 1, r = v[A - 1] - v[0];

    cout << dv(l, r) - 1; //得到边界，求的是边界的低值，最后减1。
    return 0;
}