算法
(贪心、排序) $O(N\log N)$
记 $S_i$ 表示青木得到的选票数,$X_i$ 表示高桥得到的选票数。 $A$ 为高桥得到的选票数和青木得到的选票数之间的差值。
一开始,高桥没在任何地方演讲,所以 $A = -\sum\limits_{i = 1}^N S_i$
若高桥在第 $i$ 个地方演讲,青木得到的选票数将少 $S_i$ 张,高桥得到的选票数将多 $S_i + X_i$ 张,而 $A$ 就需要加上 $2S_i + X_i$,所以我们不妨将每个 $S_i$ 乘以 $2$ 再加上 $X_i$。
为了让高桥得到的选票数更多且演讲的次数尽可能少,那么显然我们应该要在 $2S_i + X_i$ 比较大的地方演讲将是最佳选择。所以我们需要对数组 $S$ 进行排序。
然后从后往前遍历每个 $S_i$,并把当前的 $S_i$ 加进 $A$,同时把答案加一,直到 $A$ 大于 $0$ 为止。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> s(n);
ll a = 0;
rep(i, n) {
int x;
cin >> s[i] >> x;
a -= s[i];
s[i] *= 2;
s[i] += x;
}
sort(s.begin(), s.end());
int ans = 0;
while (a <= 0) {
a += s.back();
s.pop_back();
++ans;
}
cout << ans << '\n';
return 0;
}