AI018. 数据分片调度

# 二分答案:对「最大段和上限 x」二分,贪心判定最少段数是否 <= k
# 下界是 max(t)(单条不可再切),上界是总和;段数可细分所以判定用 <=
import sys


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    k = int(data[1])
    t = [int(x) for x in data[2:2 + n]]

    def feasible(cap: int) -> bool:
        seg = 1
        cur = 0
        for x in t:
            if x > cap:
                return False
            if cur + x > cap:
                seg += 1
                cur = x
            else:
                cur += x
        return seg <= k

    lo = max(t)
    hi = sum(t)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)


if __name__ == "__main__":
    solve()