二分查找的泛化应用

很多竞赛题不会直接给你一个有序数组让你查找，而是需要你从问题中抽象出一个单调函数，然后对它的自变量进行二分搜索。

2.1 核心解题框架

解决这类问题的步骤如下：

确定自变量 x：题目要求的最值（如最小速度、最大载重）往往就是 x。
确定单调函数 f(x)：写出一个函数，输入 x，能计算出在 x 条件下的结果。f(x) 必须是关于 x 的单调函数（递增或递减）。
确定目标值 target：题目给出的约束条件，如时间限制、天数限制等，就是 target。
套用二分搜索模板：根据题目要求（求最小值还是最大值），决定使用左侧边界还是右侧边界模板。

代码框架：

// 单调函数，具体实现根据题目而定
int f(int x, /* 其他参数 */) {
    // 计算在条件 x 下的结果
}

int solve(/* 参数 */) {
    int left = x的最小可能值;
    int right = x的最大可能值 + 1; // 使用左闭右开区间

    while (left < right) { // 这里使用左闭右开写法更常见于泛化二分
        int mid = left + (right - left) / 2;
        if (f(mid) <= target) { // 满足约束，尝试更小的 x
            right = mid;
        } else {
            left = mid + 1; // 不满足约束，必须增大 x
        }
    }
    return left;
}

图示： alt text

2.2 例题一：爱吃香蕉的珂珂

题目描述：有 N 堆香蕉，第 i 堆有 piles[i] 根。警卫将在 H 小时后回来。珂珂每小时可以吃掉一堆中的 K 根（如果一堆少于 K 根，就全吃掉，且这一小时内不能再吃别的）。求能在 H 小时内吃完所有香蕉的最小速度 K。

输入格式：

第一行：两个整数 N 和 H，表示香蕉堆数和限制时间。
第二行：N 个整数，表示每堆香蕉的数量。

输出格式：

一个整数，表示最小速度 K。

样例输入：

4 8
3 6 7 11

样例输出：

解题分析：

自变量 x：吃香蕉的速度 K。
函数 f(x)：速度为 x 时，吃完所有香蕉需要的小时数。f(x) 是单调递减的（速度越快，时间越少）。
目标 target：H 小时。
要求：求最小的 x，使得 f(x) <= H。这是典型的左侧边界。

代码实现（ACM模式）：

#include <iostream>
#include <vector>
using namespace std;

// 计算速度为 x 时所需的小时数
long long hoursNeeded(vector<int>& piles, int x) {
    long long hours = 0;
    for (int p : piles) {
        hours += p / x;
        if (p % x != 0) {
            hours++;
        }
    }
    return hours;
}

int minEatingSpeed(vector<int>& piles, int H) {
    int left = 1;
    int right = 1e9 + 1; // 最大速度是最大堆的香蕉数，取一个足够大的上界

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (hoursNeeded(piles, mid) <= H) {
            right = mid; // 速度够快，尝试更慢的速度（向左搜索）
        } else {
            left = mid + 1; // 速度太慢，必须加快
        }
    }
    return left;
}

int main() {
    int N, H;
    cin >> N >> H;
    vector<int> piles(N);
    for (int i = 0; i < N; i++) {
        cin >> piles[i];
    }
    cout << minEatingSpeed(piles, H) << endl;
    return 0;
}

alt text

2.3 例题二：在 D 天内送达包裹的能力

题目描述：传送带上的包裹必须按顺序在 D 天内运完。第 i 个包裹的重量为 weights[i]。每天装载的重量不能超过船的最大运载能力。求能在 D 天内运完所有包裹的最低运载能力。

输入格式：

第一行：两个整数 N 和 D，表示包裹数量和限制天数。
第二行：N 个整数，表示每个包裹的重量。

输出格式：

一个整数，表示最低运载能力。

样例输入：

10 5
1 2 3 4 5 6 7 8 9 10

样例输出：

解题分析：

本题与“爱吃香蕉的珂珂”本质相同。
自变量 x：船的运载能力。
函数 f(x)：运载能力为 x 时，需要的天数。单调递减。
目标 target：D 天。
要求：求最小的 x，使得 f(x) <= D。

代码实现（ACM模式）：

#include <iostream>
#include <vector>
using namespace std;

int daysNeeded(vector<int>& weights, int cap) {
    int days = 0;
    for (int i = 0; i < weights.size(); ) {
        int dailyLoad = 0;
        while (i < weights.size() && dailyLoad + weights[i] <= cap) {
            dailyLoad += weights[i];
            i++;
        }
        days++;
    }
    return days;
}

int shipWithinDays(vector<int>& weights, int D) {
    int left = 0, right = 0;
    for (int w : weights) {
        left = max(left, w); // 最小运力至少是单个包裹的最大重量
        right += w;          // 最大运力是所有包裹重量和
    }
    // 注意：这里使用左闭右开区间，所以 right 要 +1
    // while (left < right) 写法下，right 初始值应为最大可能值 + 1
    int right_bound = right + 1; 
    while (left < right_bound) {
        int mid = left + (right_bound - left) / 2;
        if (daysNeeded(weights, mid) <= D) {
            right_bound = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int N, D;
    cin >> N >> D;
    vector<int> weights(N);
    for (int i = 0; i < N; i++) {
        cin >> weights[i];
    }
    cout << shipWithinDays(weights, D) << endl;
    return 0;
}

*学习笔记

暂没有学习笔记，快来抢first blood ！

2.1 核心解题框架​

2.2 例题一：爱吃香蕉的珂珂​

2.3 例题二：在 D 天内送达包裹的能力​

*学习笔记​

2.1 核心解题框架

2.2 例题一：爱吃香蕉的珂珂

2.3 例题二：在 D 天内送达包裹的能力

*学习笔记