塔子哥の视频带读讲解 | 塔子哥学算法

# 塔子哥の视频带读讲解

基础算法-二分答案|华为4月12日实习笔试 (opens new window)

# 塔子哥の点评

在笔试中，二分搜索很少作为单独的考点来考察，95%的情况下是考察更进阶的知识点:二分答案。

# 入门教程

# 二分搜索

这个部分网上的优质资源太多了，我这里给大家推荐代码随想录的详解。

二分法入门 by Carl (opens new window)

# 二分答案

这个部分网上也有优质资源，但是塔子哥始终没找到非常适合我们专栏的教程。所以塔子哥决定自己写一篇知识点精讲。一步步带大家入门二分答案!

# 例题1

先来看一道真题:P1189. 华为实习 2023.04.12-实习笔试-第一题-购物系统的降级策略 (opens new window)

1.化简题意

给你一个数组 $R$ ，寻找一个最大的阈值 $v$ ，满足条件 $T:\sum min(R_i,v) \leq cnt$

2.观察性质

1.条件一定能满足:设定 $v = 0$ , $sum(min(v,R_i))= 0$

2. $v$ 越大 , 条件越难满足: $v \rightarrow \infty$ , 那么就不会有 $R_i$ 被取 $min$ , 这个时候总和是最大的。

上述是考虑两个极端情况，也是最容易理解的情况。但是相信大家能够感受到单调性了：随着 $v$ 的增大 , 总和就会增大，那么条件 $T$ 就越难成立。

3.图形化显示

为了能够更直观的显示单调性，我们规定: 条件不满足时， $T = 0$ 。条件满足时 $T = 1$ 。那么可以想象这个 $T$ 应该随着 $v$ 的增大，先 $1$ 后 $0$ , 如图所示:

分析

题目要寻找的正是断崖下降的那个断崖点。从另一个角度来说，我们的问题就变成了，<给你一个先1后0的数组，你需要找到最后一个 $1$ 的位置>，这不正是二分搜索可以解决的问题么？只不过注意一点：这里的数组更加抽象，因为我们没办法直接 $O(1)$ 获取这个数组里的每一个数，而是需要通过一定的计算来获取数组里每个元素的值。

至此，通过一步一步的分析，拨开云雾之后，大家可以明白二分答案本质还是二分搜索。只不过我们二分的横坐标是答案。而原先二分搜索的横坐标通常是数组下标。

4.解决思路

1.二分 $v$ 来找数组里的最后一个1

2.获取“数组”里这个位置的值：对于每个确定的 $v$ , 我们直接求解 $\sum min(R_i,v) \leq cnt$ 这个逻辑表达式。成立返回1，不成立返回0

5.代码实现

# 读入
R = list(map(int,input().split()))
cnt = int(input())
# 查询数组里的第i位值
def check (i):
    su = 0
    for x in R:
        su += min(i , x)
    return su <= cnt
# 设定v的边界
l , r = 0 , 10**9
while l <= r:
    mid = l + r >> 1
    if check(mid):
        l = mid + 1
    else:
        r = mid - 1
# 这种情况即题目描述的第一种情况,等价于"数组"全1 , 那么右端点不会动
if r == 10**9:
    r = -1
print(r)

# 例题2

再来看一道LeetCode经典二分题:LeetCode 875. 爱吃香蕉的珂珂 (opens new window)

1.化简题意:

给你一个数组 $a$ ，寻找一个最小的值 $k$ ，满足条件 $T:\sum \lceil\frac{a_i}{k}\rceil \leq h$

2.观察性质(单调性)

$k$ 越小，条件越难满足。 $k$ 越大 , 条件越容易满足

3.图形化

条件成立 $T = 1$ , 反之 $T = 0$ , 那么本质为:给定一个先0后1的数组,找第一个 $1$

4.思路

1.二分 $v$ 来找数组里的第一个1

2.获取“数组”里这个位置的值：对于每个确定的 $v$ , 我们直接求解 $\sum \lceil\frac{a_i}{k}\rceil \leq h$ 这个逻辑表达式。成立返回1，不成立返回0

5.代码实现

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 查询数组里的第i位值
        def check (i):
            su = 0
            for x in piles:
                su += (x - 1) // i + 1
            return su <= h
        # 设定v的边界
        l , r = 1 , 10**9
        while l <= r:
            mid = l + r >> 1
            if check(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

# 总结

1.二分答案，顾名思义，针对答案的二分。

2.它是一种更加抽象(广义)的二分搜索，所以学习它需要二分搜索作为前置知识。

3.解题关键:

1.化简题意，寻找答案和要满足的条件 $T$

2.判断条件 $T$ 是否根据答案具有单调性(令成立为 $1$ , 不成立为 $0$ )

3.转化成二分搜索(先1后0的数组找最后一个1 / 先0后1的数组找第一个1)

# 代码仓库

# 例题1

# C++

#include<bits/stdc++.h>

using namespace std;
int n = 0;
int x[101000];
int a;

int check(int now) {
    long long all = 0;
    for (int i = 0; i < n; i++) {
        all += min(x[i], now);
    }
    return all <= a;    
}

int main() {
    long long sum = 0;
    while (cin >> x[n]) {
        sum += x[n];
        n++;
    }
    n--;
    a = x[n];
    sum -= a;
    if (sum <= a) {
        printf("-1");
        return 0;
    }
    int l = -1, r = a + 1;
    while (l + 1< r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if(check(r))
        printf("%d", r);
    else
        printf("%d", l);
    return 0;
}

# Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str = in.nextLine().split(" ");
        int[] nums = new int[str.length];
        for(int i = 0; i < str.length; i++){
            nums[i] = Integer.parseInt(str[i]);
        }
        int cnt = in.nextInt();
        long sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum <= cnt){
            System.out.println(-1);
            return;
        }
        int value = 100010;
        int l = 0, r = value;
        while(l < r){
            int mid = l + r + 1>> 1;
            if(check(mid, nums, cnt)){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        System.out.println(l);
    }
    private static boolean check(int value, int[] nums, int cnt){
        long sum = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] < value){
                sum += nums[i];
            }else{
                sum += value;
            }
        }
        if(sum <= cnt) return true;
        return false;

    }
}

# Go

package main
import(
    "fmt"
    "sort"
)
func main(){
    var arr []int
    var num int
    for{
        _, err := fmt.Scanf("%d", &num)
        if err == nil{
            arr = append(arr, num)
        }else{
            break
        }
    }
    var cnt int
    fmt.Scanln(&cnt)
    sort.Ints(arr)
    ans := getResult(arr, cnt)
    fmt.Println(ans)
}

func getResult(arr []int, cnt int)int{
    n := len(arr)
    pre := make([]int, n + 1)
    for i := 1 ; i <= n ; i++{
        pre[i] = pre[i - 1] + arr[i - 1]
    }
    if cnt >= pre[n]{
        return -1
    }
    if cnt < n{
        return 0
    }
    l := -1
    r := arr[n - 1]
    for l < r{
        mid := (l + r) / 2
        index := sort.SearchInts(arr, mid)
        if arr[index] == mid{
            index += 1
        }
        sum := pre[index] + mid * (n - index)
        if sum <= cnt{
            l = mid + 1
        }else if sum > cnt{
            r = mid
        }
    }
    return l - 1
}

# Js

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function(){
    let input1 = await readline()
    let nums = input1.split(" ").map(v=>parseInt(v))
    let maxsum = parseInt(await readline())
    let sum = nums.reduce((p,c)=>p+c)
    if(sum <= maxsum){
        console.log(-1)
        return
    }

    const n = Math.floor(maxsum/nums.length)
    let left = n,right = maxsum
    while(left<=right){
        let mid = (right+left)>>1
        if(caclSum(nums,mid)>maxsum) right = mid-1
        else{
            left = mid+1
        }
    }
    console.log(right)
    function caclSum(nums,val){
        let arr = nums.slice()
        if(arr[0]>val)arr[0] = val
        return arr.reduce(
            (p,c)=>{
                if(c>val) c=val
                return (p+c)
            }
        )
    }

})()

# 例题2

# 见力扣官方题解

← 数位dp 题单 →