[バックアップ][Python][Greedy]ATM

📃 質問する

仁河銀行には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人あたりの引き出しに要する時間のプロトコルの最大値を出力します.

💻 問題を解く

"""Code1"""
# time : 16 

n = int(input())
time = list(map(int, input().split()))

time.sort()
for i in range(1,n):
    time[i] = time[i-1] + time[i]

print(sum(time))

"""Code2"""
# time : 3

n = int(input())
time = list(map(int, input().split()))

time.sort()
cur = 0
sum_value = 0
for ts in time:
    cur += ts
    sum_value += cur

print(sum_value)

キー(Key)

sort()を使用して、小さな値から開始します.

反復文を1から実行し、現在の値(i)と以前の値(i-1)を加えて、現在のtime[현재 index]に格納します.

sum()を使用して、時間のすべての値を加算します.

Code1とCode2は時間的に異なる.
最後のprint(sum(time))部分のためかもしれませんが、差が小さすぎるのでCode1で説明できます.