P2440 题解

题目传送门

提取关键词，题目需要的是数量大于 $k$ 的最大 $l$，考虑二分答案。

可以二分枚举 $l$ 的值，check函数中检验切割出该长度小段木头的个数，与 $k$ 进行比较。

小数据模拟

例如，我们有五根木棍且 $k=4$，分别为3 7 4 10 6

第一次循环 $l=0,r=9,mid=4$。check函数中得到 $ans=0+1+1+2+1=5>k$,所以增大小段木头的长度使 $l=mid$ 。

第二次循环 $l=4,r=9,mid=6$。得到 $ans=0+1+0+1+1=3<k$，少于题目中需要的数量，所以需要缩短小段木头的长度使 $r=mid$。

第三次循环 $l=4,r=6,mid=5$ 得到 $ans=0+1+0+2+1=k$，返回true使 $l=mid$。

此时 $l=5,r=6。l+1=r$ 跳出循环，答案储存在 $l$ 中返回 $l$ 的值。

code:

#include <bits/stdc++.h>
#define int long long
#define MAXN 0x3f3f3f3f3f3f3f3f
#define MINN -0x3f3f3f3f3f3f3f3f
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;

const int N=1e5+29;
int n,k,maxn;
int a[N];

bool check(int x){//x表示小段木头的长度
    int ans=0;
    for(int i=1;i<=n;i++) ans+=a[i]/x;//枚举每根原木，将能从这根原木中切割出长度为x的小段木头的数量累加到ans中
    return ans>=k;//这里取了等号给l
}
int binary(){
    int l=0,r=maxn+1;//这里l最好从0开始,r从maxn+1开始，避免出锅
    while(l+1<r){//老师讲的最原始的方法【也是我觉得最好理解的
        int mid=l+r>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    return l;//因为等号给了l，所以答案储存在l里
}

signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxn=max(maxn,a[i]);//用于确定二分中r的初始值
    }
    cout<<binary();
    return 0;
}

注意事项：

注意二分中=给的对象，若 $l$ 取到=，答案储存在 $l$ 中，反之则在 $r$ 中。

二分中建议初始化 $l=0，r=maxn+1$ 避免出现一些难调的bug

如果担心不能切割的情况，即答案为 $0$ 时会出错，可在main函数中特判：

    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum<k){
        cout<<0;
        return 0;
    }