题解 | #餐馆#

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> tables(n);
    for(int i = 0; i < n; i ++){
        cin >> tables[i];
    }

    vector<pair<int, LL>> guests(m);
    for(int i = 0; i < m; i ++){
        cin >> guests[i].first >> guests[i].second;
    }

    // 排序桌子和客人
    sort(tables.begin(), tables.end());
    sort(guests.begin(), guests.end());
    // 优先队列
    priority_queue<pair<LL, int>> max_heap;

    LL total_income = 0;
    int guest_index = 0;

    // 遍历每张桌子
    for(int capacity : tables){
        // 将所有可以坐下的客人放入优先队列，按消费金额降序排列
        while(guest_index < m && guests[guest_index].first <= capacity) {
            max_heap.push({guests[guest_index].second, guests[guest_index].first});
            guest_index ++;
        }

        if(!max_heap.empty()) {
            total_income += max_heap.top().first;
            max_heap.pop();
        }
    }

    cout << total_income << endl;

    return 0;
}