AtCoder Beginner Contest 187 D - Choose Me - おじさんの競プロ記録

問題

問題文へ

N個の町があり、i番目の町には青木派の有権者が $A_i$ 人、高橋派の有権者が $B_i$ 人います。他に有権者はいません。

高橋氏は、それぞれの町で演説を行うことができます。

高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。

一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。

高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？

制約

入力はすべて整数
${1 \leqq N \leqq 2 \times 10^5}$
${1 \leqq A_i,B_i \leqq 10^9}$

考えたこと

高橋氏が演説をすれば、 $A_i,B_i$ を手にします。演説をしないならば、青木氏が $A_i$ を手にします。

まったく演説をしないと、高橋氏0票対青木氏は $A_i$ の合計です。逆にすべての町で演説をすると、高橋氏は ${A_i,B_i}$ の合計に対して青木氏は0票です。

求められているのは、最小でいくつの町で演説をするかです。スタートは演説をしない状態で、そこから一番多く票をもらえる町から演説していくことにします。

ある町で演説すると、高橋氏は ${A_i,B_i}$ 票を得ます。同時に青木氏は $A_i$ 票を失います。高橋氏は1つの町で ${2A_i + B_i}$ 票を得ます。

これをあらかじめ計算し、降順にソートしておきます。

得票数の多い順に、青木氏の最大得票数から引いていき、0を下回れば勝つことができます。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    ll N;
    cin >> N;

    vector<ll> v(N);
    ll A_sum = 0;
    rep(i, N) {
        ll a, b;
        cin >> a >> b;
        A_sum += a;
        v[i] = a * 2 + b;
    }

    sort(v.rbegin(), v.rend());
    ll ans = 0;
    while (A_sum >= 0) {
        A_sum -= v[ans];
        ++ans;
    }

    cout << ans << endl;
    
    return 0;
}

解説を読んで

X=（高橋氏の得る票数）-（青木氏の得る票数）と定義する。これができてなかったです。式をたてることが大事なのではないかと思います。