华华给月月准备礼物

题意

有N个给定长度的木棍，华华想得到K条长度(L)相同的木棍(给定的木棍可裁剪)，最大化L。

思路

容易想到可以二分长度，对于每个长度，暴力check一下能不能裁成大于等于K条木棍。

复杂度

代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;

int n, k;
int a[maxn];

bool check(int x){
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans += a[i] / x;
        if(ans >= k)
            return 1;
    }
    return 0;
}

int main()
{
    int l = 0, r = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        r = max(r, a[i]);
    }
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}