A29698.木材加工

这题算是一道模板题，我就不讲了还是简单讲一讲吧

首先，解法肯定是二分，细分有两种方法
1.查找长度，判断木头段数是否达标
2.查找段数，判断木头长度是否达标
这里采用了前者

给出代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;    //ll替代long long的一种写法

const ll MAXN=100005;
ll a[MAXN];
ll n, k;

bool is_TRUE(ll len){    //用于判断段数是否达标
    ll cnt=0;
    for(ll i=1; i<=n; i++)
        cnt+=a[i]/len;
    return cnt>=k;
}

int main(){
    cin >> n >> k;
    ll max_len=0;
    for(ll i=1; i<=n; i++){
        cin >> a[i];
        max_len=max(max_len, a[i]);
    }

    ll l=1, r=max_len, mid, ans=0;    //这里采用变量标记法
    while(l<=r){    //因为是变量标记法，不能排除i==r
        mid=(l+r)/2;
        if(is_TRUE(mid)){    //还能再长
            ans=mid;    //标记
            l=mid+1;
        }
        else
            r=mid-1;
    }

    cout << ans;
    return 0;
}

实际上二分核心代码还有不用ans标记变量的写法:

    ll l=0, r=max_len, mid;    //不用ans变量标记
    while(l<r){    //因为此时l会成为最终答案
        mid=(l+r+1)/2;    //向上取整
        if(is_TRUE(mid)){    //还能再长
            l=mid;    //确认答案，不能+1
        }
        else
            r=mid-1;
    }
    cout << l;    //输出l
    return 0;

欢迎加入团队