tooh’s diary

半角全角、常体敬体が入り乱れるカオス

Python3でまったり競技プログラミング 3日目(二分探索)

続かね〜〜〜〜〜〜wwwwwwwwwwwwwww

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D&lang=jp

n,k = map(int,input().split())
W = []
for i in range(n):
    W.append(int(input()))
l = max(W)-1
#トラックの積載容量は少なくとも「荷物の中で一番重いもの」を乗せられなければならない
#二分探索では、lは「これを下回ってはいけない」値に相当するので、-1しておく
#(↑一つの荷物がバカ重い場合とかは、答えがmax(W)になることは当然ある)
W.append(10**13) #1つのトラックで10**6の重さを10**6個積まないといけない場合を想定
h = sum(W)
while l+1 < h:
    ok = (l+h)//2
    track = 0
    cur = 0
    for i in range(n+1):
        cur += W[i]
        if cur > ok:
            track += 1
            cur = W[i]
        elif cur == ok:
            if i != n-1: #最後は番兵で絶対に数える事になるから、i == n-1の場合だけは数えないでおく
                track += 1
                cur = 0
    if track > k:
        l = ok
    else:
        h = ok
print(h)