[AtCoder] ABC 187 D – Choose Me

2021年2月3日

問題

方針

まず初めに演説を行わなかったときを考えます。青木君得票数は \( A_i \) の総和なので、その得票数を \( s_0 \) とすると、

\[ s_0 = \sum_{i = 1}^{N}B_i\]

となります。また、高橋君の得票数を \( t_0 \) とすると、\( t_0 = 0 \) です。

ここで、\( i \) 番目の町で演説をするかどうかを決めた後の青木君と高橋君の得票数をそれぞれ、\( s_i, t_i \) とします。\( i \) 番目の町で演説を行うと、得票数は、

\begin{eqnarray}
s_i &=& s_{i – 1} – A_i \\
t_i &=& t_{i – 1} + A_i + B_i\\
\end{eqnarray}

と変化します。\( s_i < t_i \) となったとき演説を新たにする必要はありません。ここで、得票数の差を計算すると、

\[ t_i – s_i = t_{i – 1} + 2A_i + B_i – s_{i-1}\]

となります。したがって、\( i \) 番目の町で演説を行うと得票数の差は、\( 2A_i + B_i \) となるので、\( 2A_i + B_i \) の大きい順に演説を行えば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    ll A[N], B[N], C[N];
    ll s = 0;
    pair<ll, ll> p;
    
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        s += A[i];
        C[i] = 2 * A[i] + B[i];
    }
    sort(C, C + N, greater<ll>());
    ll t = 0;
    for (int i = 0; i < N; i++) {
        t += C[i];
        if (t > s) {
            cout << i + 1 << "\n";
            return 0;
        }
    }
    return 0;
}