Educational Codeforces Round 75 E2. Voting (Hard Version)

お題箱より。

問題概要

選挙の投票者が $n$ 人いて、全員が自分を支持するようにしたい。投票者 $i$ が自分を支持する条件は2つあり、どちらかを満たすと支持する。

全員に自分を支持させるために必要な金額の最小値を求めよ。

$1 \le t \le 2\times 10^{5}$ の複数テストケースで、各ケースは以下を満たす。

支持者0の状態から、1人ずつ順番に支持者を選んで増やしていくことを考えます。このとき買収金額最小化の裏返しとして、「買収せずに支持させる投票者の $p_{i}$ の合計を最大化する」ように支持者を選んでいきます。

既に $x$ 人の支持者がいて、次に $x+1$ 人目の支持者を選ぶ時のことを考えます。このときの選択としては、

とするのが最適となります。その理由は、各ステップであえて損する選択（安い人を支持させたり、買収なしで支持させられる人がいるのに買収を選んだり）をしたときに、後でその損した分を上回るほどの得ができることはないからです。

これは優先度付きキューを使ってシミュレーションすることができます。具体的には支持者が $x$ 人であるような段階それぞれについて、まず $m_{i} = x$ であるような人の買収金額 $p_{i}$ を優先度付きキューに入れ、その後キューが空でなければ最大要素を１つキューから出せば良いです。

そして最後までキューに残った人たちが買収の対象になるので、その人たちの $p_{i}$ の合計が答えになります。