洛谷P2440 木材加工 题解

这是我找到的一篇很久之前为了让我更好理解二分写的详细题解

题目链接

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;
    }