讨论/《滴滴历届真题汇总》 - 2019 卷 2:魔法权杖强化/
《滴滴历届真题汇总》 - 2019 卷 2:魔法权杖强化
共 1 个回复

二分搜索

#include<bits/stdc++.h>
using namespace std;
int arr[100005];
int n,m;

bool isOk(long mid){
    int cnt = 0;
    long sum = 0;
    for(int i =0;i<n&&cnt<=m;i++){
        if(sum>=mid){
            sum = 0;
        }
        sum+=arr[i];
        if(sum<mid){
            cnt++;
        }
    }
    return cnt<=m;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i =0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    long l = 1,r = INT_MAX*10L;
    while(l<r){
        long mid = (l+r+1)/2;
        if(isOk(mid)){
            l = mid;
        }else{
            r = mid-1;
        }
    }
    cout<<l<<endl;

    return 0;
}