問題
AtCoder 市で市長選挙が行われます。候補者は青木氏と高橋氏です。
市には N 個の町があり、i 番目の町には青木派の有権者が A_i 人、高橋派の有権者が B_i 人います。他に有権者はいません。
高橋氏は、それぞれの町で演説を行うことができます。
高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。
一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。
高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？
制約
- 入力は全て整数
- 1 <= N <= 2 * 10^5
- 1 <= A_i, B_i <= 10^9
考えたこと
とりあえず総当たりでやると2^n通りのパターンがあり時間に間に合わないので、何かしらひと工夫する必要がある。
パッと思いついたのは貪欲法。自然に考えて人口が多い市で演説した方がお得そうだから。
ということで人口の多い市(A_i + B_i)が多い順にソートして、多い方からk個の市に演説に行き、投票数を計算して最小のkを探すというのをやってみる。ここは別に計算量はnでもいいのでforループで探す(たぶん二分探索なら若干早くなる)。
そしてとりあえず出してみるとWA。9個も違うのでわりと普通に間違っているらしい。
よく考えてみると人口が同じ市の優先度をつけていなかったことに気づく。
総人口が同じとき、青木派は演説すると寝返ってくれるため、青木派が多い方が青木票を削れるためおいしい。どれくらいおいしいかというと、演説したときに青木派については高橋票が増えて青木票が減る。一方高橋派については高橋票が増えるのみである。
ということで今度はその価値(A[i]+A[i]+B[i])が高い順にソートして同じようにやってみる。
AC。よかった。
