【題解】Codeforces 1379C. Choosing flowers

【題目敘述】http://codeforces.com/contest/1379/problem/C

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int t, n, m, a[100005], b[100005];
long long suf[100005], tot, mx;
vector <int> no;
 
int main() {
    cin >> t;
    while (t--){
        cin >> n >> m;
        no.clear();
        for (int i = 1; i <= m; i++){
            cin >> a[i] >> b[i];
            no.push_back(a[i]);
        }
        no.push_back(0);
        sort(no.begin(), no.end());
        suf[m+1] = 0;
        for (int i = m; i >= 1; i--){
            suf[i] = suf[i+1]+no[i];
        }
        mx = 0;
        for (int i = 1; i <= m; i++){
            int pos = upper_bound(no.begin(), no.end(), b[i])-no.begin();
            pos = max(pos, m-n+1);
            tot = suf[pos];
            pos = n-(m-pos+1);
            if (a[i] <= b[i]){
                tot += a[i];
                pos--;
            }
            tot += (long long)b[i] * pos;
            mx = max(mx, tot);
        }
        cout << mx << "\n";
    }
}
分享本文 Share with friends