# 塔子哥の视频带读讲解
基础算法-二分答案|华为4月12日实习笔试 (opens new window)
# 塔子哥の点评
在笔试中,二分搜索很少作为单独的考点来考察,95%的情况下是考察更进阶的知识点:二分答案。
# 入门教程
# 二分搜索
这个部分网上的优质资源太多了,我这里给大家推荐代码随想录的详解。
二分法入门 by Carl (opens new window)
# 二分答案
这个部分网上也有优质资源,但是塔子哥始终没找到非常适合我们专栏的教程。所以塔子哥决定自己写一篇知识点精讲。一步步带大家入门二分答案!
# 例题1
先来看一道真题:P1189. 华为实习 2023.04.12-实习笔试-第一题-购物系统的降级策略 (opens new window)
1.化简题意
给你一个数组,寻找一个最大的阈值,满足条件
2.观察性质
1.条件一定能满足:设定 ,
2.越大 , 条件越难满足: , 那么就不会有 被取 , 这个时候总和是最大的。
上述是考虑两个极端情况,也是最容易理解的情况。但是相信大家能够感受到单调性了: 随着 的增大 , 总和就会增大,那么条件 就越难成立。
3.图形化显示
为了能够更直观的显示单调性,我们规定: 条件不满足时, 。条件满足时 。那么可以想象这个应该随着的增大,先 后 , 如图所示:
分析
题目要寻找的正是断崖下降的那个断崖点。 从另一个角度来说,我们的问题就变成了,<给你一个先1后0的数组,你需要找到最后一个的位置>,这不正是二分搜索可以解决的问题么?只不过注意一点:这里的数组更加抽象,因为我们没办法直接获取这个数组里的每一个数,而是需要通过一定的计算来获取数组里每个元素的值。
至此,通过一步一步的分析,拨开云雾之后,大家可以明白 二分答案本质还是二分搜索。只不过我们二分的横坐标是答案。 而原先二分搜索的横坐标通常是数组下标。
4.解决思路
1.二分 来找数组里的最后一个1
2.获取“数组”里这个位置的值:对于每个确定的 , 我们直接求解 这个逻辑表达式。成立返回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.化简题意:
给你一个数组,寻找一个最小的值,满足条件
2.观察性质(单调性)
越小,条件越难满足。 越大 , 条件越容易满足
3.图形化
条件成立 , 反之 , 那么本质为:给定一个先0后1的数组,找第一个
4.思路
1.二分 来找数组里的第一个1
2.获取“数组”里这个位置的值:对于每个确定的 , 我们直接求解 这个逻辑表达式。成立返回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.化简题意,寻找答案 和 要满足的条件
2.判断条件 是否根据答案具有单调性(令成立为 , 不成立 为 )
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)
}
)
}
})()