技術室奥プログラミングコンテスト#4 Day1：K - 天使と宿題

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k

解法

最終日には必ず写させてもらう必要がある．なぜならば，最終日分の宿題は N - 1 日までで写すことができないから．最終日で写せるページ数 (a_N) 日分は写すことができるので，次に (N - a_N) ~ (N - 1) 日目の間で絶対写させてもらう必要があるので，最も a_i が大きい日に写させてもらう．このように，後ろから貪欲に写しに行く日が決まっていく．これは std::priority_queue を用いて O(NlogN) で実装できる．