[python]李珂太大数法則

7166 ワード
algorithm テキストリンク
💡 だいすうのほうそく
就職のためのコードテストwith Python(羅東彬)
: 92p

質問する


  • 異なる数の配列がある場合、与えられた数をM回加算して最大数の法則を生成する.

  • 配列内のインデックスの数はKを超えることはできません.
    [2, 4, 5, 4, 6], M=8, K=3
    ⇒ 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46

  • 異なるインデックスが同じ数を持つ場合は、異なるとみなされます.
    [3, 4, 3, 4, 3], M=7, K=2
    ⇒ 4 + 4 + 4 + 4 + 4 + 4 + 4 = 28

    • 入力条件

  • 第1行は、N(2≦N≦1000)、M(1≦M≦10000)、K(1≦K≦10000)の自然数を与え、各自然数はスペースで区切られる.
  • 行目にはN個の自然数がある.各自然数はスペースで区切られています.ただし、自然数ごとに1以上10000以下の数です.
  • 入力によって与えられるKは、常にM以下である.

    • しゅつりょくじょうけん

  • の最初の行では、東彬の大数の法則に基づいて、加算された答えが出力されます.

    • 入力例

    5 8 3
2 4 5 4 6

    出力例

    46

    に答える


    アイデア

  • 階調アルゴリズム
    -貪欲な方法で、今の状況で、今すぐ良いものを選ぶ方法
    -現在の選択が今後に与える影響を考慮せずに、すべての瞬間に最もよく見えるものを選択します.
    • 降順に
  • 、大きいから小さいまで
    • を並べます.
  • 最大数K回を加え、K回を超えて2番目に大きい数を加え、その後最大数K回(M回)
    • を加える.

    コード#コード#

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

data.sort(reverse=True)
result = 0

while True:
    for i in range(k):
        if m == 0:
            break
        result += data[0]
        m -= 1
    if m == 0:
        break
    result += data[1]
    m -= 1

print(result)
    💡 Mの大きさが100億を超えると?
    ◇繰り返される数列を知る
    [2, 4, 5, 4, 6], M=8, K=3
    ⇒ (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = 46

  • 重複数列の長さ:(K+1)
    ◇Mを(K＋1)に分けた部重複数列の回数
    ここにKを乗じて、最も多く出現したのは
    ◇Mが(K+1)に分けられない場合、残りの最大数が増加する

  • 増加した最大数量:M//(K+1)*K+M%(K+1)
    • n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[n - 1]
second = data[n - 2]

count = m // (k + 1) * k
count += m % (k + 1)

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

print(result)
    ナノ編集ステーションで降りる
    Verticaのこれらのこと(12)-verticaのバックアップとリカバリ