BOJ 2343その他のコース

4205 ワード
2021.02.03 テキストリンク
https://www.acmicpc.net/problem/2343
2秒、128 MBメモリ
input :
  • N M(1 ≤ N ≤ 100,000)(1 ≤ M ≤ N)
  • その他の課程の長さは課程順に分単位(自然数)
    • である.
    output :
  • 出力最小ブルーレイサイズ
    • どのような面を探るべきですか?思い出せない.
    可能な限り長い青色光の最大長と最小長の範囲の間に値を見つけなければなりません.
    見つかったmid値にチュートリアルを加えて、ブルーレイが何個あるかを決定します.
    import sys

n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

lo = max(data)
hi = sum(data)
while lo <= hi:
    mid = (lo + hi) // 2
    cnt = 0
    full = 0
    for item in data:
        if full + item > mid:
            cnt += 1
            full = 0
        full += item
    if full > 0:
        cnt += 1

    if cnt > m:
        lo = mid + 1
    else:
        hi = mid - 1

print(lo)
    while条件には<=が必要です.
    hi=mid-1なので、私たちはずっと-1の値を持っていて、答えではありません.計算に成功すれば、最後にlo=mid+1の演算でloに答えを得ることができます.
    ソートできない問題なので、loを最初に初期化するときにmax(data)を使用します.
    4th Development Practice
    [TIL] NoSQL