题意: 华华希望裁剪出至少根木棍,并且木棍的长度越长越好。
题解: 简单思考一下,发现二分最大长度即可,每次二分的时候表示判定以为当前木棍的最大长度是否可剪出至少根木棍,如果可以说明最大长度至少为,若不行则说明长度最长为的时间复杂度为,总时间复杂度为


代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
int q[N], n, k;

ll check(int x) {
    ll res = 0;
    for(int i = 0; i < n; i++) res += q[i] / x;
    return res;
}

int b_s(int l, int r, ll k) {
    //l,r是木棍的长度 
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check(mid) >= k) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    scanf("%d%d", &n, &k);

    int Ma = 0;
    for(int i = 0; i < n; i++) 
        scanf("%d", &q[i]), Ma = max(Ma, q[i]);

    int t = b_s(0, Ma, (ll)k);
    printf("%d\n", t);

    return 0;
} 

另:由于题目中说的初始木棍长度是非负整数,而数据范围给的,也许这就是二分的左边界不能为1的原因?(希望会的大佬可以教教我QwQ