[Baekjoon] 2613. デジタルビーズ[2]

7754 ワード
バックアップアルゴリズム テキストリンク

📚 質問する


最低価格の問題!バイナリ探索で解決する.
x x x x x x o o o o o o o o o..
最低価格は最小値なので上のように出てきます.
したがって、バイナリ検索では、パラメータ検索を使用して、満たされた最も左側の値を検索できます.
最大値がxの場合、実行可能かどうかを検索する関数を作成する必要があります.
再帰関数を使用しました.
左から、最低価格以下の数字を詰められるビーズを組み合わせに詰めます.
このとき重要なのは、各グループに数字のビーズがあり、充填するときに残りのグループ数に従ってビーズを1つ残してグループに充填することです.
積算和を用いてビーズが最高価格より小さいかどうかを判断する.
最後のビーズを加えて、欲しい最高値より大きければ終わりです.

📒 コード#コード#

def check(cur, prv):
    global mid
    if cur == m - 1:
        if arr[-1] - arr[prv] <= mid:
            visited.append(n - prv)
            return True
        return False
    nxt = -1
    for i in range(prv + 1, n - m + cur + 2):
        if arr[i] - arr[prv] > mid:
            break
        nxt = i

    if nxt != -1:
        visited.append(nxt - prv)
        return check(cur + 1, nxt)

    return False


n, m = map(int, input().split())
arr = [0] + list(map(int, input().split()))

s, e = max(arr), sum(arr)
for i in range(1, n + 1):   # 누적합
    arr[i] += arr[i - 1]

ans = 0
while s <= e:
    visited = []
    mid = (s + e) // 2
    if check(0, 0):
        e = mid - 1
        ans = mid
        result = visited[:]
    else:
        s = mid + 1
print(ans)
print(*result)

🔍 結果


回転:DataTable重複除外(プログラム例比較)
単純なSingleton単一モード