有基础班_第九课_二分答案（一）

zxcvbnm

2025-06-20 12:38:31

发布于：上海

25阅读

0回复

0点赞

题目
【二分答案】砍树
木材加工
数段分列

【二分答案】砍树

题目大意

给定 $N$ 棵树的高度，Mirko 需要至少 $M$ 米的木材。

Mirko 可以设定伐木机锯片的高度 $H$ ，将所有比 $H$ 高的树砍掉上方部分并收集这些部分木材。现在他希望 找到最大的锯片高度 $H$ ，使得总获得木材长度不少于 $M$ 米。

题意分析

如果锯片设得太低，砍得多，容易超过需求；
如果锯片设得太高，砍得少，可能达不到需求；
目标是找一个 最大的 满足要求的 $H$ ，使得砍到的木材 $\ge M$ 米。

这正好符合 二分答案 的模型。

解题思路

1. 二分查找的范围：

最低为 0（不砍）
最高为数组中的最大树高（不能超过任何树）

2. 检查函数 `check(H)`：

判断如果锯片高度为 $H$ ，是否能获得 $\ge M$ 米的木材。

bool check(int H) {
    long long sum = 0;
    for 每棵树高度 h:
        if(h > H)
            sum += h - H;
    return sum >= M;
}

3. 二分流程

while(l <= r) {
    int mid = (l + r) / 2;
    if(check(mid)) {
        ans = mid;  // 记录当前满足条件的H
        l = mid + 1;  // 尝试更大的H
    } else {
        r = mid - 1;  // 砍得太少，降低高度
    }
}

时间复杂度分析

每次二分需要遍历一遍数组，复杂度是 $O(N)$ ；
二分的次数是 $\log_2(\max(h))$ ，最多约 30 次；

总时间复杂度： $O(N \log h_{\text{max}})$ ，可接受。

代码演示

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

typedef long long ll;

int n;
ll m;
vector<int> a;

// 检查当前锯片高度 H 是否能砍到至少 m 米木材
bool check(int H) {
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] > H)
            sum += a[i] - H;
    }
    return sum >= m;
}

int main() {
    cin >> n >> m;
    a.resize(n);

    int max_h = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        max_h = max(max_h, a[i]);
    }

    int l = 0, r = max_h;
    int ans = 0;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;      // 记录当前可行解
            l = mid + 1;    // 尝试更大的 H
        } else {
            r = mid - 1;    // 木材不足，降低 H
        }
    }

    cout << ans << endl;
    return 0;
}

木材加工

题目大意

给定 $n$ 根原木的长度，要求将它们切割成 $k$ 段长度相同的木头，问这种情况下 每段长度 $l$ 的最大可能值。如果无法切出 $k$ 段，输出 $0$ 。

题意分析

原木可以有剩余。
每段小木头长度必须是整数。
要求所有小段的长度相同，且段数不少于 $k$ 。
求能满足条件的最长长度 $l$ 。

解题思路

这是一个二分答案的经典题目：

单调性：段长 $l$ 越大，能切出来的段数越少；
所以可以二分枚举段长 $l$ ，检查是否能切出至少 $k$ 段。

核心函数 `check(l)`：

判断长度为 $l$ 时是否能切出至少 $k$ 段木头。

遍历所有原木；
对于每根木头 $L_i$ ，它最多能切出 $L_i / l$ 段；
累加所有段数，判断是否 $\ge k$ 。

时间复杂度解析

二分的次数是 $\log(\max L_i)$ ；
每次 check 都要遍历 $n$ 根木头，复杂度是 $O(n)$ ；
总复杂度是 $O(n \log L_{\max})$ ，可以处理 $n \le 10^5$ 。

代码演示

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

typedef long long ll;

int n, k;
vector<int> wood;

// 检查是否能用长度 l 切出至少 k 段
bool check(int l) {
    if (l == 0) return false; // 不能切成长度为 0 的段
    ll cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += wood[i] / l;
    }
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    wood.resize(n);
    int maxlen = 0;
    for (int i = 0; i < n; ++i) {
        cin >> wood[i];
        maxlen = max(maxlen, wood[i]);
    }

    int l = 1, r = maxlen, ans = 0;

    // 二分答案
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;     // 当前满足，记录答案
            l = mid + 1;   // 尝试更大的长度
        } else {
            r = mid - 1;   // 尝试更小的长度
        }
    }

    cout << ans << endl;
    return 0;
}

数列分段

题目大意

给定一个长度为 $N$ 的数列 $A$ ，将其分成 $M$ 段，每段必须连续。要求这些段的段和最大值尽可能小，求这个最小的可能值。

题意分析

目标是：划分 $M$ 段，使得这 $M$ 段中最大段和最小。

例如：

数列为 [4, 2, 4, 5, 1]
要求分为 3 段
[4][2 4][5 1]：段和分别为 4、6、6，最大段和为 6
这是最优方案

解题思路

这是典型的二分答案 + 贪心验证问题。

1. 单调性说明（为什么可以二分）：

如果我们尝试的最大段和是 $x$ ，并且成功将数列分为不多于 $M$ 段；
那么我们尝试更大的段和（如 $x+1$ ）也一定可以；
所以这是一个**“可行性单调性问题”，可以二分答案**。

check 函数定义

给定最大段和限制为 mid，判断是否可以把整个数组划分成不超过 $M$ 段。

bool check(int mid) {
    int cnt = 1;      // 至少一段
    int sum = 0;      // 当前段的和
    for (int i = 0; i < n; i++) {
        if (sum + a[i] <= mid) {
            sum += a[i];  // 当前段继续累加
        } else {
            cnt++;        // 需要开新的一段
            sum = a[i];   // 当前段从a[i]开始
        }
    }
    return cnt <= m; // 是否划分段数不超过M
}

时间复杂度解析

check 每次 $O(n)$
二分最多 $\log(\sum a_i)$ 次
总体复杂度： $O(n \log(\sum a_i))$ ，可接受

代码演示

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

typedef long long ll;

int n, m;
vector<int> a;

// 检查是否能以最大段和不超过 mid 的方式分成不超过 m 段
bool check(int mid) {
    int cnt = 1;    // 初始一段
    int sum = 0;    // 当前段的和

    for (int i = 0; i < n; ++i) {
        if (a[i] > mid) return false; // 单个元素都超过mid，非法

        if (sum + a[i] <= mid) {
            sum += a[i];
        } else {
            cnt++;
            sum = a[i];
        }
    }

    return cnt <= m;
}

int main() {
    cin >> n >> m;
    a.resize(n);

    int maxA = 0;
    ll total = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        maxA = max(maxA, a[i]);
        total += a[i];
    }

    int l = maxA, r = total, ans = total;

    while (l <= r) {
        int mid = (l + r) / 2;

        if (check(mid)) {
            ans = mid;       // 可以满足，尝试更小
            r = mid - 1;
        } else {
            l = mid + 1;     // 不满足，需要更大
        }
    }

    cout << ans << endl;
    return 0;
}