In order that Takahashi obtains more votes than Aoki, it is important to increase the number of votes that Takahashi obtains, and decrease the number of votes that Aoki obtains.
Now let \(X = {}\) (the number of Takahashi’s votes) \(-\) (the number of Aoki’s vote). Then one can see that:

• \(X\) increases by \(2A_i+B_i\) if he makes a speech in town \(i\)
• Once \(X > 0\) is satisfied, Takahashi gets more votes than Aoki

Therefore, it is optimal to make speech in the towns with larger \(2A_i + B_i\) first, until \(X>0\) satisfied. The time complexity is \(O(N \log N)\).

Sample Code (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = int64_t;

int main(){
    ll N;
    cin >> N;
    ll X = 0;
    vector<ll> x(N);
    for(ll i = 0; i < N; i++){
        ll A, B;
        cin >> A >> B;
        X -= A;
        x[i] = A + A + B;
    }
    sort(x.begin(), x.end());
    ll ans = 0;
    while(X <= 0){
        X += x.back();
        x.pop_back();
        ans++;
    }
    cout << ans << endl;
}

Sample Code (Python)

N = int(input())
X = 0
x = []
for i in range(N):
    A, B = map(int, input().split())
    X -= A
    x.append(A + A + B)
x.sort()
ans = 0
while X <= 0:
    X += x.pop()
    ans += 1
print(ans)