画匠问题

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int n, k;
    cin>>n>>k;
    ll a[n+1], x, Max=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        Max = max(Max, a[i]);
    }
    ll l = Max, r = INT64_MAX>>2, m, s, cnt;
    while(l<r){
        s = cnt = 0;
        m = (l+r)>>1;
        for(int i=0;i<n;i++){
            if(m < s+a[i]){
                s = a[i];
                cnt++;
            }else
                s += a[i];
        }
        if(s)
            cnt++;
        if(cnt > k)
            l = m+1;
        else
            r = m;
    }
    cout<<l<<endl;
    return 0;
}

def solution(arr, num):  # 工作清单和工人数目 | O(N*logS), S=sum(arr)
    assert arr and len(arr) and num
    if len(arr) <= num:  # 如果工人过多，则是取最长的一个工作返回
        return max(arr)

    def get_need_num(limit):  # 每个画师只能工作不超过limit的时间，问需要几个画师才能完成
        res, worked = 1, 0  # 已用画师数目， 当前画师已工作时间
        for v in arr:
            if v > limit:  # 这一幅画哪怕单独分配给一个画师也完成不了
                return float('inf')
            worked += v
            if worked > limit:  # 如果尝试画当前的画已超工时
                res += 1  # 新增一个画师来画这幅画
                worked = v  # 新增画师的当前工时为v
        return res

    min_sum, max_sum = 0, sum(arr)  # 二分法确定每个画师的最大工作量
    while min_sum != max_sum - 1:
        mid = (min_sum + max_sum) // 2
        if get_need_num(mid) > num:
            min_sum = mid
        else:
            max_sum = mid
    return max_sum

n, num = map(int, input().split())
arrs = list(map(int, input().split()))
print(solution(arrs, num))