【アルゴリズム問題】yukicoder no.21 平均の差 by くろとんさん (レベル☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.21 平均の差 by くろとんさん (レベル☆)

2014-09-03 00:24

    N個の数字が与えられるのでこれらをK(>=3)個のグループに振り分ける。
    ただし各グループには最低一つ数字が含まれているとする。

    ex) 例えば 与えれる数字が {10,3,23,91,5}, K=3 なら
    {{3,91},{23,5},{10}} のような振り分けかたはただしく
    {{},{3,5,10},{23,91}} のような振り分けかたは認められません

    グループごとに平均を計算し, それらをもとに 最大の平均 - 最小の平均 を計算し、
    最後に小数点以下を切り上げその値を「平均の差」と呼ぶ。
    平均の差を最も大きくするようなグループ分けをしたとき、平均の差はいくつになるか答えよ。

    【入力】
    N
    K
    n1
    n2
    ...
    nN

    1行目にはN(3<=N<=9)が与えられる。
    2行目にはK(3<=K<=N)が与えられる。
    3行目~N+2行目には数字(1<=Ni<=1000)が与えられる。

    【出力】
    答えの数値を文字列で出力してください。

    【sample1】
    5
    3
    555
    20
    432
    301
    21

    【ans1】
    535

    例えば {{555}, {21,20}, {433,301}} のようにグループ分けすると
    平均は {555/1, (21+20)/2, (432+301)/2} = {555, 20.5, 366.5} なので
    最大の平均 - 最小の平均は 555-20.5 = 534.5
    最後に小数点以下を切り上げて535

    【sample2】
    8
    4
    329
    980
    656
    738
    739
    542
    873
    501

    【ans2】
    651

    【question】
    9
    4
    210
    340
    274
    997
    313
    66
    330
    12
    842


    1st. nanashiさん Ruby
    http://ideone.com/D6eUSt

    2nd.ヒロソフさん C++
    http://ideone.com/5CBpoO
    C#
    http://ideone.com/nMQqiI

    3rd. なおさん WhiteSpace
    http://ideone.com/GvZbnL


    4th.nanashiさん
    http://ideone.com/grbTSQ
    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。