バックアップ-AT(11399)

Greedy

質問する

仁河銀行にはATMが1台しかありません.今このATMの前にN人が並んでいます.人は1番からN番まで、i番の引き出しにかかる時間はPi分です.
人々が並んでいる順番によって、お金を引き出すのにかかる時間の和が違います.例えば、P 1=3、P 2=1、P 3=4、P 4=3、P 5=2の合計5人とする.[1.2.3.4.5]順番に並んでいれば、1番の人は3分以内にお金を引き出すことができます.2番の人は1番の人がお金を引くまで待たなければならないので、3+1=4分です.3番の人は1番2番の人がお金を引き出すまで3+1+4=8分かかります.4番は3+1+4+3=11分、5番は3+1+4+3+2=13分です.この場合、1人当たりの引き出しに要する時間の合計は、3+4+8+11+13=39分である.
[2,5,1,4,3]順に並び、2番が1分、5番が1+2=3分、1番が1+2+3=6分、4番が1+2+3+3=9分、3番が1+2+3+3+4=13分です.1人当たりの引き出しに要する時間の合計は1+3+6+9+13=32分です.この方法よりも必要な時間の和を最小限に抑えることはできない.
並んでいる人数Nと一人当たりの引き出しに要する時間Piを指定する場合は、一人当たりの引き出しに要する時間のプロトコルの最大値を求めるプログラムを作成してください.

入力

1行目は人数N(1≦N≦1000)を与える.2行目は一人一人がお金を引き出すのに必要な時間Piを与えます.(1 ≤ Pi ≤ 1,000)

しゅつりょく

1行目は、1人あたりの引き出しに要する時間のプロトコルの最大値を出力します.

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

def solution():
    answer = 0
    
    for i in range(n):
        for j in range(0, i + 1):
            answer += arr[j]
    return answer

print(solution())
        

基本的なギリシャ問題.2番目の入力を昇順に整理して続行します.