算法题：木材加工

问题描述

木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原本的长度都是正整数，我们要求得到的小段木头的长度也是正整数。

输入格式

第一行是两个正整数N和K(1≤N≤100000，1≤K≤200000)，N是原木的数目，K是需要得到的小段的数目。接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度L。

输出格式

输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出“0”．

样例

输入

3 7
232
124
456

输出

114

解决方案

思路

二分答案

代码

#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    int m = 0;
    int arr[100005];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        m = max(m, arr[i]);
    }

    int l = 0;
    int r = m;
    while (r - l > 1) {
        int mid = (l + r) / 2;

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += arr[i] / mid;
        }

        if (ans >= k)
            l = mid;
        else
            r = mid;
    }

    cout << l;

    return 0;
}