SamCoding Round 9 (Div. 4) D - Printer Queue
- サイト
- SamCoding
- コンテスト
- SamCoding Round 9 (Div. 4)
- 問題
- D - Printer Queue(常設版)
人の生徒が 1 台のプリンターで書類を印刷します。生徒 の書類の印刷には 秒かかります。プリンターは一度に 1 つの書類しか印刷できず、時刻 から休みなく順に印刷します。各生徒の待ち時間を「時刻 から自分の書類が印刷し終わるまでの時間」とするとき、印刷する順番をうまく決めて、待ち時間の合計の最小値を求める問題です(、)。
印刷時間の短い順に印刷するのが最適です。
番目に印刷する書類の印刷時間を とすると、 番目の生徒の待ち時間は です。待ち時間の合計では、 は 番目以降の 人の待ち時間に含まれるので、
になります。前に印刷するものほど大きな係数が掛かるので、短いものを前に置けばよいです。
実際、隣り合う があれば、2 つを入れ替えると合計は だけ減ります。そのため、最適な順番では印刷時間が短い順に並んでいます。
あとは をソートして累積和をとり、その合計を出力すれば答えです。 です。
Python
from itertools import accumulate
input()print(sum(accumulate(sorted(list(map(int, input().split()))))))accumulate でソート後の累積和、つまり各生徒の待ち時間を求め、その合計を出力しています。