【二分答案】工资

题

---

解

二分答案。本来还想着DP或者二分答案再优化优化的，一看数据范围能过就不管了。

---

代码

#include<cstdio>
#define ll long long
ll n,m,l,r,mid;
ll k[1000005];
bool pd(ll zz){
   ll lj = 0,sl = 0; //累计值，数量
   for(int i = 1; i <= n; ++i){  //逐个累加，看看需要分段数量是否大于mid
        if(lj + k[i] <= zz) lj += k[i];
        else{
           lj = k[i];
           ++sl;
        }
        if(lj > zz || sl > m) return 0;
    }
    if(sl+1 > m) return 0;
    return 1;   
}
int main(){
    scanf("%lld%lld", &n, &m);
    for(ll i = 1; i <= n; ++i){
        scanf("%lld", &k[i]);
        r += k[i];
    }
    l = 0;
    while(l<r){  //二分
        mid = (l+r) >> 1;
        if(pd(mid) == 0) l = mid + 1;
        else r = mid;
    }  
    printf("%lld",r);
}