二分答案转化为判定

发表于

一个最优化问题抽象为函数

其定义域为该问题下的可行方案

对这些方案的评估值就是值域

假设评分越高越优，若最优解的评分是S，显然对于所有>S的值，都不存在一个合法方案达到该值，否则就与S的最优矛盾。而对于所有<S的值，一定存在一个合法的方案达到或超过该评分

这样问题就具有一种特殊的单调性

在S的一侧合法，在另一侧不合法

可以通过二分找到这个分界点S

这样，我们就把一个求最优解的问题转化为给定一个值mid，判定是否存在一个可行方案评分达到mid

例1

有N本书排成一行，已知第i本的厚度为Ai

把它们分成连续的M组，使T最小化，其中T表示厚度之和最大的一组的厚度

题中出现了 最大值最小 答案具有单调性，可以用二分法

我们将 把书划为M组的方案作为定义域

厚度之和最大一组的厚度作为值域

假设最终答案为S，因为S的最优性，如果要求每组的厚度都<S,那么这M组一定无法容纳全部的书，可能需要更多的组才能分完。如果每组的厚度可以>S,那么一定存在一种分数方案使得组数不超过M

意味着对于本题的限制条件不存在可行的分书方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool valid(int size){
    int group=1,rest=size;
    for(int i=1;i<=n;++i){
        if(rest>=a[i])rest-=a[i];
        else group++,rest=size-a[i];
    }
    return group<=m;
}
int main(){
    int l=0,r=sum_of_ai;
    while(l<r){
        int mid=(l+r)/2;
        if(valid(mid))r=mid;
        else l=mid+1;
    }
}

例2

NOIP2015跳石头

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0 。

接下来 N 行，每行一个整数，第 i 行的整数 Di(0<Di<L) ， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

输入样例

1
2
3
4
5
6
25 5 2 
2
11
14
17 
21

输出样例

1
4

说明

输入输出样例 1 说明：

将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4 (从与起点距离 17 的岩石跳到距离 21的岩石,或者从距离 21 的岩石跳到终点)。

另：对于 20% 的数据, 0≤M≤N≤10 。

对于 50% 的数据, 0≤M≤N≤100 。

对于 100% 的数据, 0≤M≤N≤50,000,1≤L≤1,000,000,000 。

思路

1
2
3
4
5
6
7
我们二分跳跃距离，然后把这个跳跃距离“认为”是最短的跳跃距离，然后去以这个距离为标准移石头。使用一个judge判断这个解是不是可行解。如果这个解是可行解，那么有可能会有比这更优的解，那么我们就去它的右边二分。为什么去右边？答案是，这个区间是递增的 ，而我们求的是最短跳跃距离的最大值，显然再右边的值肯定比左边大，那么我们就有可能找到比这更优的解，直到找不到，那么最后找到的解就有理由认为是区间内最优解。反过来，如果二分到的这个解是一个非法解，我们就不可能再去右边找了。因为性质，右边的解一定全都是非法解。那么我们就应该去左边找解。整个过程看起来很像递归，实际上，这个过程可以递归写， 也可以写成非递归形式，我个人比较喜欢使用非递归形式。

下一个问题，这个judge怎么实现呢？judge函数每个题有每个题的写法，但大体上的思想应该都是一样的——想办法检测这个解是不是合法。拿这个题来说，我们去判断如果以这个距离为最短跳跃距离需要移走多少块石头，先不必考虑限制移走多少块，等全部拿完再把拿走的数量和限制进行比对，如果超出限制，那么这就是一个非法解，反之就是一个合法解，很好理解吧。

可以去模拟这个跳石头的过程。开始你在i(i=0)位置，我在跳下一步的时候去判断我这个当前跳跃的距离，如果这个跳跃距离比二分出来的mid小，那这就是一个不合法的石头，应该移走。为什么？我们二分的是最短跳跃距离，已经是最短了，如果跳跃距离比最短更短岂不是显然不合法，是这样的吧。移走之后要怎么做？先把计数器加上1，再考虑向前跳啊。去看移走之后的下一块石头，再次判断跳过去的距离，如果这次的跳跃距离比最短的长，那么这样跳是完全可以的，我们就跳过去，继续判断，如果跳过去的距离不合法就再拿走，这样不断进行这个操作，直到i = n+1，为啥是n+1？河中间有n块石头，显然终点在n+1处。（这里千万要注意不要把n认为是终点，实际上从n还要跳一步才能到终点）。

模拟完这个过程，我们查看计数器的值，这个值代表的含义是我们以mid作为答案需要移走的石头数量，然后判断这个数量 是不是超了就行。如果超了就返回false，不超就返回true。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#define maxn 500010
using namespace std;
int d,n,m;
int a[maxn];
int l,r,mid,ans;
inline int read(){//我喜欢快读
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
        if (c == '-') flag = true;
    else
        num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

bool judge(int x){//judge函数，x代表当前二分出来的答案
    int tot = 0;//tot代表计数器，记录以当前答案需要移走的实际石头数
    int i = 0;//i代表下一块石头的编号
    int now = 0;//now代表模拟跳石头的人当前在什么位置
    while (i < n+1){//千万注意不是n，n不是终点，n+1才是
        i++;
        if (a[i] - a[now] < x)//判断距离，看二者之间的距离算差值就好
            tot++;//判定成功，把这块石头拿走，继续考虑下一块石头
        else
            now = i;//判定失败，这块石头不用拿走，我们就跳过去，再考虑下一块
    }
    if (tot > m)
        return false;
    else
        return true;
}

int main(){
    d = read();//d代表总长度，也就是右边界
    n = read();//n块石头
    m = read();//限制移走m块，思考的时候可别被这个m限制
    for (int i=1;i<=n;i++)
        a[i] = read();
    a[n+1] = d;//敲黑板划重点，再强调一遍，n不是终点
    l = 1;//l和r分别代表二分的左边界和右边界
    r = d;
    while (l <= r){//非递归式二分正常向写法，可理解为一般框架
        mid = (l+r) / 2;//这再看不出是啥意思可以退群了
        if (judge(mid)){//带入judge函数判断当前解是不是可行解
            ans = mid;
            l = mid + 1;//走到这里，看来是可行解，我们尝试看看是不是有更好的可行解
        }
        else
            r = mid - 1;//噫，你找了个非法解，赶紧回到左半边看看有没有可行解
    }
    cout << ans << endl;//最后的ans绝对是最优解
    return 0;
}

总结

二分法判定有两个条件:有界和单调

一般涉及 最大值最小 或 最小值最大的问题都可以用二分法判定来解