技術室奥プログラミングコンテスト#4 Day1：E - Osmium_1008と課題

問題
解法
解答

問題

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

解法

まず A の和が E 以下であればエナジードリンクは飲まなくてもよい．

そうでないとき，エナジードリンクを B_i が大きい順に飲んでいけばよい．B を降順にソートしておき，E に B_i を足していく．A <= E となったとき，これ以上エナジードリンクを飲む必要はないため i 本を答えとすればよい．

もし K 本飲んでも A > E であるとき，全ての課題を終わらすのは無理であるということ．なので，A を昇順にソートし，前から和を求めていく．このときの和が E を超えたとき，その課題以降は全て達成できないので，その課題より前の課題の数を答えとすればよい．O(NlogN + MlogM + K)．