[USACO] 2022_Feb. Sleeping in Class [Bronze] [BOJ - 24620_G4]

6248 ワード
USACO テキストリンク

📚 質問する


https://www.acmicpc.net/problem/24496
目標はすべての数字を同じにすることです.
最初は配列の値を変えて計算してみましたが、時間の複雑さは中では解決しにくいです.そして、構想そのものも描けない.
バイナリ探索でも解けない理由は,3を統一しても4,5以上の数にはならない可能性があるからである.したがって,バイナリ探索も不可能である.
入力したものを一種類の数字で作って、ミネラルウォーターでしかできないというアイデアを思いつきました.
薬という考えが大切だ.そこで,パラメータ探索により,約数で行えるかどうかを調べる.
累計してもいいです.1 2 3 1 1 1の累計合計は1 3 6 7 8 9です.
=>最後のインデックスの数以下の3の倍数を加算すると3になります!
したがって,パラメータ探索では,1つの方法で累積することができる.
しかし積算加算でなくても、加算して一定の数ができるかどうかをチェックするので、積算加算では解決しません.

📒 コード#コード#

def check(x):   # 매개변수 탐색, x가 가능한지 확인
    total = 0
    for i in range(n):
        if total > x:
            return False
        total += arr[i]
        if total == x:
            total = 0
    return True


for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    mmax = 0
    total = 0
    zero_cnt = 0

    for i in range(n):      # 최댓값, 최솟값 구하기
        if mmax < arr[i]:
            mmax = arr[i]
        if arr[i] == 0:
            zero_cnt += 1
        total += arr[i]

    ans = 0
    for i in range(max(1, mmax), total + 1):    # 최댓값 이상부터 가능하니 그 때부터 체크
        if total % i == 0 and check(i):         # 나누어떨어지면 그 수로 가능한지 확인
                ans = n - total // i
                break
    print(ans)

🔍 結果


鍵の説明
[TIL]階調アルゴリズム