Codeforces Round #657 (Div. 2) C题

枚举bi，找到大于bi的所有ai

#include <bits/stdc++.h>//代码来源某位不知名大佬
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        ll n, m; cin >> n >> m;
        vector<pll> arr(m);
        for (int i = 0; i < m; ++i) cin >> arr[i].first >> arr[i].second;
        sort(arr.begin(), arr.end());
        vector<ll> front(m + 1), prefix(m + 1);
        for (int i = 0; i < m; ++i) {
            front[i + 1] = arr[i].first;
            prefix[i + 1] = prefix[i] + arr[i].first;
        }
        ll ans = 0;
        for (int i = 0; i < m; ++i) {
            int ind = upper_bound(front.begin(), front.end(), arr[i].second) - front.begin() - 1;
            ind = max(ind, (int)(m - n + 1));
            ll res = prefix.back() - prefix[ind];
            ll rem = n - (m - ind);
            res += (i >= ind? arr[i].second * rem: arr[i].first + arr[i].second * (rem - 1));
            ans = max(ans, res);
        }
        ans = max(ans, prefix.back() - prefix[max(0LL, m - n)]);
        cout << ans << '\n';
    }
    return 0;
}

链接: Codeforces Round #657 (Div. 2) C题.

本文地址：https://blog.csdn.net/Peiris_/article/details/107497211