Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 229 C 問題 Cheese

AtCoder ABC ABC229 C問題 300 pts

問題

提出解答

問題の概要

$N$ 個のチーズがあり, $i$ 番目のチーズの美味しさは $A_i$ /[g] で, $B_i$ [g] である. 合計 $W$ [g] 以下のチーズを使って, 美味しさを最大にせよ.

制約

$1 \leq A,B \leq 10^{18}$
$A,B$ は整数

解法

美味しさが大きい順から使うべきである. よって, 必要ならば添字を入れ替えて, $A_1 \geq \dots \geq A_N$ としてもよい. このとき, 以下のようにして正解を導くことができる.

の順に以下を実行する.
- $U:=\min(W,B_i)$ とする ( $U$ が使うチーズの重さ).
- $X$ に $A_i U$ を加算し, $W$ から $U$ を引く.

計算量はソートがボトルネックになり, $O(N \log N)$ である.