[Fishen]このcote-Greedyアルゴリズム,大数法則(実戦問題)

グレースケールアルゴリズム

ギリシャ語の意味は「貪欲」です
つまり、現在の状況では、現在良いものだけを選ぶ方法は

です.
✔[問題の説明]

董斌の大数法則は、異なる数の配列がある場合、与えられた数をM回加算し、最大数を形成する法則である.ただし,配列の特定のインデックスの数はK回を連続して超えることはできない.
配列の大きさN,数値加算の回数M,Kが与えられると,結果が出力される.

[入力条件]

第1行N(2<=N<=1000)、M(1<=M<=10000)、K(1<=K<=10000)の自然数であり、自然数は

をスペースで区切る.

K <= M

第2行にはN個の自然数があり、スペース区切り(1<=自然数<=10000)

ex)
5 8 3
2 4 5 4 6->46出力
[合成コード]

n,m,k = map(int, input().split())
data = list(map(int,input().split()))
data.sort() #정렬 
first = data[n-1]
second = data[n-2]

result = 0 

while True:
    for i in range(k):
        if m == 0:
            break
          
        result += first
        m -= 
        
    if m == 0:
        break
    result += second
    m -= 1

print(result)

入力:583n 2 4 4 6
出力:46

forゲートまでは、自分で考えて書くことができますが、次のifゲートは本を参考にしています.ゼロになる例外をよく考えなければならない.

[例の回答]

n,m,k = map(int, input().split())
data = list(map(int,input().split()))
data.sort() #정렬 
first = data[n-1]
second = data[n-2]

#가장 큰 수가더해지는 횟수 계산
count = int(m/(k+1)) * k
count += m % (k+1)

result = 0
result += (count) * first 
result += (m-count) * second

print(result)

📌

上のコードはMが大きくなるとタイムアウトと判定されます

の数列を利用して

にアクセスする.

665/66/6665、すなわち数列の長いは(K+1)

である.

Mを数列の長さで割ると、繰り返しの回数が得られます.ここでK値を乗じると出現回数が最も多い.

点が取れない場合を考慮し、残りの最大数を追加します.

int(M/(k+1)) * k + M % (k+1)

@これはPythonを使用した符号化テストです