Franz`s blog

基础算法-二分答案

二分答案：

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。OI-WIKI

二分答案模板

寻找 >= 的最小值

1
2
3
4
5
6
7
8
9
10
11
int bserach_l(int l, int r, int x)
{
    while (l < r) {
        int mid = l + ((r - l) >> 1); // 防止溢出
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

寻找 <= 的模板

1
2
3
4
5
6
7
8
9
10
11
int bserach_l(int l, int r, int x)
{
    while (l < r) {
        int mid = l + ((r - l) >> 1) + 1; // 防止溢出
        if (check(mid))
            r = mid;
        else
            l = mid - 1;
    }
    return l;
}

例题

例题 P2440 木材加工

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n,k;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        int max = 0;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            max = Math.max(max,arr[i]);
        }
        int l = 1 , r = max;
        int val = 0;
        int maxVal = 0;
        int res = 0;
        while(l <  r){
            int mid = l + ((r - l) >> 1);
            val = getChunkNums(arr,mid);
            if (val < k){
                r = mid;
            }else{
                l = mid + 1;
                if (mid >= res){
                    res = mid;
                    maxVal = val;
                }
            }

        }
        System.out.println(maxVal >= k ? res : 0);
    }

    public static int getChunkNums(int[] arr,int l){
        int res = 0;
        for (int i1 = 0; i1 < arr.length; i1++) {
            res += arr[i1] / l;
        }
        return res;
    }
}