luogu-P2440 木材加工

GESP C++ 五级练习题，二分答案和贪心思想考点应用，五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P2440 木材加工

题目要求

题目背景

要保护环境。

题目描述

木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。

木头长度的单位是 $\text{cm}$，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 $11$ 和 $21$，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$。

输入格式

第一行是两个正整数 $n,k$，分别表示原木的数量，需要得到的小段的数量。

接下来 $n$ 行，每行一个正整数 $L_i$，表示一根原木的长度。

输出格式

仅一行，即 $l$ 的最大值。

如果连 $\text{1cm}$ 长的小段都切不出来，输出 0。

输入输出样例 #1

输入 #1

3 7
232
124
456

输出 #1

114

说明/提示

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 10^5$，$1\le k\le 10^8$，$1\le L_i\le 10^8(i\in[1,n])$。

题目分析

本题是一个典型的“二分答案”题目。

我们需要找到一个最大的长度 $l$，使得这 $n$ 根原木能切割出至少 $k$ 段长度为 $l$ 的木头。 容易发现，如果长度 $l$ 可行，那么对于任何小于 $l$ 的长度 $l'$ 也一定可行（因为更短的木头更容易切出来）；反之，如果长度 $l$ 不可行，那么对于任何大于 $l$ 的长度 $l''$ 也一定不可行。 这种单调性满足二分答案的条件。因此，我们可以对**答案（木头长度）**进行二分查找，将求最大值问题转化为判别问题（Check 函数）。

解题思路

1. 确定二分区间：
   • 下界 $l$：最小可能的正整数长度为 1。
   • 上界 $r$：能够切割出的最长木头长度不可能超过最长的一根原木。因此，$r = \max(L_i)$。
2. 编写 Check 函数：
   • 函数签名：bool check(int mid)，判断长度 $mid$ 是否满足条件。
   • 逻辑：遍历每一根原木，计算每根原木能切出多少段长度为 $mid$ 的木头。对于长度为 $L_i$ 的原木，能切出的段数为 $\lfloor L_i / mid \rfloor$。
   • 统计总段数 cnt。如果 cnt >= k，说明长度 $mid$ 可行，返回 true；否则返回 false。
   • 注意：总段数可能会很大，虽然 $k$ 最大为 $10^8$ 在 int 范围内，但在计算过程中最好使用 long long 以防万一（特别是在累加过程中）。
3. 二分查找过程：
   • 初始化 $l=1, r=\max(L_i)$，答案 $ans=0$。
   • 当 $l \le r$ 时，取中间值 $mid = l + (r - l) / 2$。
   • 调用 check(mid)：
     • 若为真（可行）：说明 $mid$ 可能是答案，但也可能存在更长的解。更新 $ans = mid$（记录当前最优解），并尝试在右半区间查找更大的值，令 $l = mid + 1$。
     • 若为假（不可行）：说明 $mid$ 太长了，必须减小长度，在左半区间查找，令 $r = mid - 1$。
4. 特殊处理：
   • 如果所有原木总长度都小于 $k$，显然连 1cm 都切不出来，直接输出 0。在代码中，ans 初始化为 0，且二分区间从 1 开始，如果 1 都不满足，ans 保持 0，也符合逻辑。
5. 复杂度分析：
   • Check 函数的时间复杂度为 $O(n)$。
   • 二分查找的次数为 $O(\log(\max(L_i)))$。
   • 总时间复杂度为 $O(n \log(\max(L_i)))$，代入数据规模计算量约为 $10^5 \times 30 \approx 3 \times 10^6$，完全满足 1秒的时间限制。

示例代码

#include <algorithm>
#include <iostream>

typedef long long ll;

// 全局数组存储每根原木的长度，大小需稍大于 10^5
int a[100005];

// check 函数：验证是否能切出 k 段长度为 mid 的木头
// mid: 当前尝试的小段木头长度
// n: 原木根数
// k: 目标段数
bool check(int mid, int n, int k) {
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += a[i] / mid;
        if (cnt >= k) {
            return true;
        }
    }
    return false;
}

int main() {
    int n, k;
    std::cin >> n >> k;
    int r = 0;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        // 确定二分查找的上界：一小段的最长长度不可能超过最长的那根原木
        r = std::max(r, a[i]);
        sum += a[i];
    }

    if (sum < k) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // 二分查找答案
    // 答案区间 [l, r] 初始化为 [1, 最长原木长度]
    int l = 1;
    int ans = 0;
    while (l <= r) {
        // 计算中间值，mid 即为当前尝试的长度
        int mid = l + (r - l) / 2;
        if (check(mid, n, k)) {
            // 如果 mid 长度可行，说明可能还有更优解（更长），向右半区间查找
            ans = mid;
            l = mid + 1;
        } else {
            // 如果 mid 长度不可行（切不够 k 段），说明 mid 太长，向左半区间查找
            r = mid - 1;
        }
    }

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

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号