ミュージックビデオ

4684 ワード
python アルゴリズム#アルゴリズム# テキストリンク
作成日:2022年1月14日午後5:27

インプリメンテーションコード

# 뮤직비디오(결정 알고리즘)
import sys
sys.stdin = open("input.txt", "rt")

def Count(capacity):
    sum = 0
    cnt = 1
    for x in music:
        if sum+x > capacity:
            cnt += 1
            sum = x
        else:
            sum += x
    return cnt

n, m = map(int, input().split())
music = list(map(int,input().split()))
maxx = max(music)
lt = 1
rt = sum(music)
res = 0

while lt <= rt:
    mid = (lt+rt)//2
    if mid >= maxx and Count(mid) <= m:
        res = mid
        rt = mid - 1
    else:
        lt = mid + 1

print(res)
  • 二分探索を利用する.(決定アルゴリズム)
  • の可能なdvdの最小容量は、1からdvdに曲をすべて置くsum(music)までである.
  • この区間は半分に分けて確認します.
  • Count関数は、特定の容量のdvdに曲を読み込むときにどれだけのdvdが必要かを求める関数です.
    • 厩舎を決める
    ローカルエリアネットワークのクリップ