A49455.探险 题解

很典的二分啊。

简单来说，有 $n$ 个数，分成 $k$ 段连续的部分，让和最小的那一组尽量大。求这个最大值。

二分这个最大值 mid，check 函数直接 $O(n)$ 跑一遍，累加，一旦累加超过 mid 直接分成一组。最后判断组数是否大于等于 $k$.

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=3e4+34;
ll n,k,l,r,ans;
ll a[MAXN];
inline bool can(const ll &mid){
    ll res=0,sum=0;
    for(ll i=1;i<=n;i++){
        sum+=a[i];
        if(sum>=mid){
            res++;
            sum=0;
        }
    }
    return res>=k;
}
int main(){
    cin>>n>>k;
    for(ll i=1;i<=n;i++) cin>>a[i];
    l=0,r=1e9;
    while(l<=r){
        ll mid=l+r>>1;
        if(can(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}