原木切割

原木切割（整数二分）

二分答案（用答案进行切分）应用满足条件：①具有左右边界、②数据具有单调性

二分答案（答案需要是单调的）就是用函数替代数组，二分的本质是删掉不存在答案的区间

某林业局现在 N 根原木，长度分别为 Xi ，为了便于运输，需要将他们切割成长度相等的 M 根小段原木（只能切割成整数长度，可以有剩余），小段原木的长度越大越好，现求小段原木的最大长度。

例如，有 3 根原木长度分别为 6,15,22，现在需要切成 8 段，那么最大长度为 5。

输入：

第一行两个整数 N, M 。（1 ≤ N ≤ 100,000，1 ≤ M ≤ 100,000,000）

接下来 N 行，每行一个数，表示原木的长度 Xi 。（1≤ Xi ≤100,000,000）

输出：

输出小段原木的最大长度， 保证可以切出 M 段。

样例：

1
2
3
4
3 8
6
15
22
1
5

1.解题思路

image-20220505071400449

  1. 根据每一个二分答案长度num[i]，利用fun()函数进行计算，求出其对应的能切出木头的段数
  2. 根据当前分出的段数s与题目给定需要切出的段数m进行比较，从而调整左右指针
  3. 当左右指针逼近到一定范围时，表示最佳答案已经找到、
  4. 判断二分的特殊类型为10类型

2.代码实现

二分答案（整数二分）即用func()函数现求函数值，替代二分查找中在数组中进行二分操作

  1. 输入数据，并动态更新二分答案的右边界
  2. 套用二分的特殊10类型相关模型进行处理
    • 根据临时长度mid与func()函数求出，原木能够切出的段数
    • 比较mid切出的段数与给定需要切出的段数进行比较，以此调整左右指针
    • 当左右指针逼近到一定范围，即找到最佳答案
  3. 输出bs()二分函数最后返回的结果
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
32
33
34
35
36
37
38
#include<iostream>
using namespace std;

int n, m, num[100005], rawr;

//求出当长度为mid时能切出的段数
int func(int x) {
    int t = 0;
    for (int i = 0; i < n; ++i) {
        t += num[i] / x;
    }
    return t;
}

//二分求解最佳值
int bs() {
    int l = 1, r = rawr;
    while (l != r) {
        int mid = (l + r + 1) / 2;
        int s = func(mid); 
        if (s >= m) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return r;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        rawr = max(rawr, num[i]);
    }
    cout << bs() << endl;
    return 0;
}