アルゴリズム忘備録

競技プログラミングとかデータ分析とか

A: Ice Tea Store - AtCoder Grand Contest 019

agc019.contest.atcoder.jp

 

アイスティーの単価がQ, H, S, D円でそれぞれ0.25l, 0.5l, 1l, 2l買える。在庫はいくらでもある。Nリットルのアイスティーを買いたいとき、必要な金額はいくらか?

 

要は2lのものをいくら買うか、ということである。まずリットル単価別にソート、もし2l以外でより安いものがあればそれで全部買う、2lが一番安い場合は2lのものを買えるだけ買い、もし1l分だけ他に欲しい場合は次に単価の安いものを買う。O(1)。