P2440 木材加工

题目背景

要保护环境。

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

输入输出样例 #1

输入 #1

1
2
3
4

3 7
232
124
456

输出 #1

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$ 是否合法，再加上这道题答案具有“单调性”，因此采取二分答案的方式，找到最大的合法的 $l$ ，时间复杂度为 $O(n \log n)$ ，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 5;
int a[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, ans = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int l = 0, r = 1e8;
    while (l <= r) {
        int mid = (l + r) / 2, sum = 0;
        if (mid == 0) {ans = 0; break;}
        for(int i = 0; i < n; i++)
            sum += a[i] / mid;
        if (sum < k) r = mid - 1;
        else {ans = mid; l = mid + 1;}
    }
    cout << ans;
    return 0;
}

P1182 数列分段 Section II

题目描述

对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。

将其如下分段：

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

输入格式

第 $1$ 行包含两个正整数 $N,M$。

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

输入输出样例 #1

输入 #1

1
2

5 3
4 2 4 5 1

输出 #1

1

6

说明/提示

对于 $20\%$ 的数据，$N\leq 10$。

对于 $40\%$ 的数据，$N\leq 1000$。

对于 $100\%$ 的数据，$1\leq N\leq 10^5$，$M\leq N$，$A_i < 10^8$， 答案不超过 $10^9$。

思路分析 + 代码实现

题目求的是“最大的最小”，所以采用二分答案的方法。对于每个 $mid$ ，检查是否能将数组分成不超过 $M$ 段，使得每段和不超过 $mid$。如果可以，说明 $mid$ 是一个可行解，尝试更小的 $mid$ ；如果不行，说明 $mid$ 太小，需要增大 $mid$ 。

二分查找的核心是判断是否能将数组分成 $cnt <= M$ 段，使得每段的和都不超过 $mid$ 。我们用变量 $acc$ 累计本段的和，当 $acc + a[i] > mid$ 时，分出一段，让 $a[i]$ 在新一段的开头，并更新 $cnt$ 和 $acc$ 。但是！有一个细节要注意，这个逻辑能正确工作，有一个隐含的前提： $mid$ 必须大于等于数组中的最大元素 $ma$ 。如果 $mid < ma$，那么数组中存在至少一个元素 $a[i] = ma$，它无法被任何一段容纳（因为 $a[i] > mid$），在这种情况下，判断的逻辑就失效了。所以在读入的过程中记录 $ma$ ，二分时将 $l$ 设为 $ma$ 即可解决。代码如下，时间复杂度 $O(n \log n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 5;
int a[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, ma = 0;
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        ma = max(ma, a[i]);
    }
    int l = ma, r = 1e9, ans;
    while (l <= r) {
        int mid = (l + r) / 2, cnt = 1, acc = 0;
        for(int i = 0; i < N; i++) {
            int t = a[i] + acc;
            if (t > mid) {
                cnt++;
                acc = a[i];
            } else acc = t;
        }
        if (cnt <= M) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << ans;
    return 0;
}