コンテンツにスキップ

SamCoding Round 9 (Div. 4) D - Printer Queue

サイト
SamCoding
コンテスト
SamCoding Round 9 (Div. 4)
問題
D - Printer Queue(常設版)

nn 人の生徒が 1 台のプリンターで書類を印刷します。生徒 ii の書類の印刷には tit_i 秒かかります。プリンターは一度に 1 つの書類しか印刷できず、時刻 00 から休みなく順に印刷します。各生徒の待ち時間を「時刻 00 から自分の書類が印刷し終わるまでの時間」とするとき、印刷する順番をうまく決めて、待ち時間の合計の最小値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤ti≤1061 \le t_i \le 10^6)。

印刷時間の短い順に印刷するのが最適です。

jj 番目に印刷する書類の印刷時間を sjs_j とすると、jj 番目の生徒の待ち時間は s1+s2+⋯+sjs_1 + s_2 + \dots + s_j です。待ち時間の合計では、sjs_j は jj 番目以降の n−j+1n - j + 1 人の待ち時間に含まれるので、

∑j=1n(n−j+1) sj\sum_{j=1}^{n} (n - j + 1) \, s_j

になります。前に印刷するものほど大きな係数が掛かるので、短いものを前に置けばよいです。

実際、隣り合う sj>sj+1s_j > s_{j+1} があれば、2 つを入れ替えると合計は sj−sj+1>0s_j - s_{j+1} > 0 だけ減ります。そのため、最適な順番では印刷時間が短い順に並んでいます。

あとは tt をソートして累積和をとり、その合計を出力すれば答えです。O(nlog⁡n)O(n \log n) です。

Python
from itertools import accumulate
input()
print(sum(accumulate(sorted(list(map(int, input().split()))))))

accumulate でソート後の累積和、つまり各生徒の待ち時間を求め、その合計を出力しています。