ABC023D

https://gyazo.com/68e0e3d12b92e4c1feaeb010f603dd63

ペナルティの最大値を最小化したい

ペナルティが時間と共に増えるのが厄介

しかもペナルティの和ではなく最大値なのが。

和なら順序の入れ替えができるので話が楽。

なんらかの貪欲な方法で順序が決まるのだろうか。

一番大きなものから取れば良いわけではない

初期値100、増加1と、初期値90増加100では後者を先にすべき

むしろ「次の値が最も大きいものを今回のものとする」が正解？

公式解説

仮の「この高さまでに割る」というリミットを用意し、残り時間の少ない順に割る

f(x)の最大化について直接貪欲法で解く方法が思いつかない時f(x)<Xの解の存在判定問題にすれば「解があるなら最大でなくても良いので1つ見つけよ」になるので貪欲アルゴリズムを見つけやすくなる

max(f(x))<tならf(x)<t