[これが符号化テスト]大数法則

Greedy Greedy
アルゴリズム理論16講
良いブログがあるのでリンクします.
だいすうのほうそく
テーマは大数の法則で、統計から学んだ大数の法則とは違います.
大きな数の問題を加えるだけです.
O(n)

answer = 0

n, m, k = map(int, input().split())

nums = list(map(int, input().split()))

nums.sort()

count = 0

for _ in range(m):
    if count < k:
        answer += nums[n - 1]
        count += 1
    else:
        answer += nums[n - 2]
        count = 0

print(answer)

最大数の草を増やすために昇順に並べます.
変数countを確立することによってkより小さいか否かを判断し,k回を超えると2番目に大きい数となる.
セットごとに加算できる最大数を加算するので、グリディアルゴリズムと考えられます.
確かな答えはあるが,この解にはO(m)の複雑さがある.nはmよりも小さいため,ソート演算を実行してもmが大きいと複雑度全体に大きな影響を及ぼさない.したがって、mが大きくなるとタイムアウトが発生する可能性があります.
見ただけでこのように解けて、もっと効果的な解があるので、少ししびれています.効率的に答えられるとは思わなかったのが、ちょっと残念でした.
乗算と除算を用いてより効果的に解く

n, m, k = map(int, input().split())

nums = list(map(int, input().split()))

nums.sort()

answer = (m // (k + 1) * k * nums[n - 1]) + (m // (k + 1) * nums[n - 2]) + (m % (k + 1) * nums[n - 1])  

乗算と除算によりmod演算は加算と複文を効果的に改善した.
まず,最大数にk回,2番目に大きい数に1回を加えることを全体と見なす.
総演算を行う必要がある回数mを(k+1)で割ったものが、1つの演算を実行する回数となる.残りは0からkの範囲の数字で、これは最後に(k+1)ブロック演算を実行し、残りの演算回数になる.
演算回数を求めると、乗算で答えを求めることができます.
部ごとにkと最大の数を乗じることができ、1は省略するが、1と2番目の大きな数を乗じると、すべての(k+1)ブロック演算を完了し、結果値を得ることができる.
残りはk番まで最大数の加算ができるので、最大数を乗じて加算すればいいです.
この解の解法演算はO(1)であるため,最も複雑なPythonのsort()複雑度はO(nlogn)である.