解説
条件に対するVi, Diの寄与を考え条件を満たす最大のねこの数を求めます。
I :こたつに入った猫の集合, S: Viの総和(全猫の大きさの総和)
条件を式にすると以下の不等式になります。
i∈I∑(Vi+Di)≤j∈/I∑Vj
以下の式を代入
j∈/I∑Vj=S−i∈I∑Vi
i∈I∑(Vi+Di)≤S−i∈I∑Vi
i∈I∑(Vi+Di)+i∈I∑Vi≤S
i∈I∑(2Vi+Di)≤S
コストを ci=2Vi+Di とおくと、条件は
i∈I∑ci≤S
となります。
この条件のもとで ∣I∣ を最大にします。
x 匹を選ぶとき、コストの合計が一番小さくなるのは、ci が小さい順に x 匹選んだときです。なので ci を昇順に並べ、合計が S を超えない範囲で前から何匹取れるかが答えになります。
ソートがあるので、計算量は O(NlogN)で実装できます。