Competitive Programming Solutions

abc187_d - Choose Me

02 Jan 2021 — Tags: greedy,sorting — URL

Greedy pick elements ordered by $2a + b$. Intuitively, we want to maximize both the contribution of a pick to oneself, $a + b$, and the loss from the other, $a$. Also, check this.

Time complexity: $O(n \log{n})$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
int solve(vector<ii> ab)
{
    auto cmp = [](ii x, ii y) {
        auto [a1, b1] = x;
        auto [a2, b2] = y;
        return 2 * a1 + b1 > 2 * a2 + b2;
    };
    auto sum_first = [](ll acc, ii x) -> ll { return acc + x.first; };
    sort(begin(ab), end(ab), cmp);
    ll atot = accumulate(begin(ab), end(ab), 0LL, sum_first), btot = 0;
    int ans = 0;
    for (auto [a, b] : ab)
    {
        btot += a + b;
        atot -= a;
        ans++;
        if (btot > atot)
            break;
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<ii> ab(n);
    for (auto &[a, b] : ab)
        cin >> a >> b;
    cout << solve(ab) << endl;
    return 0;
}

Related posts