题解 | #餐馆# 贪心

朴素做法，分别排序桌子和客人，再逐个安排

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    vector<pair<long, long>> customers; // 人数--金额 数对
    vector<pair<long, bool>> desks; // 容量-是否占用 数对
    cin >> n >> m;
    long temp1, temp2;
    for (long i = 0; i < n; i++) {
        cin >> temp1;
        desks.emplace_back(temp1, false);
    }
    // 将桌子能容纳的人数按从小到小排序
    sort(desks.begin(), desks.end(), [&](const auto & a, const auto & b) {
        return a.first < b.first;
    });
    for (long i = 0; i < m; i++) {
        cin >> temp1 >> temp2;
        customers.emplace_back(temp1, temp2);
    }
    // 将客人消费金额按从大到小排序
    sort(customers.begin(), customers.end(), [&](const auto & a, const auto & b) {
        return a.second > b.second;
    });

    long ans = 0, used = 0; // 金额，已占用桌子数
    for (long i = 0; i < m; i++) {
        // 如果最大的桌子都坐不下这批人，跳过
        if (desks[n - 1].first < customers[i].first) {
            continue;
        }
        // 如果没有空余桌子了，跳出
        if (used == n) {
            break;
        }
        for (long j = 0; j < n; j++) {
            // 找到第一个容量足够且空余的桌子
            if (desks[j].first >= customers[i].first && desks[j].second == false) {
                desks[j].second = true; // 把桌子标记为已占用
                ans += customers[i].second;
                used++;
                break;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

时间复杂度：

1、对桌子容量进行排序的时间复杂度为O(nlogn)，其中n为桌子的数量

2、对客人消费金额进行排序的时间复杂度为O(mlogm)，其中m为客人的数量

3、遍历每个客人并在桌子中查找可用桌子的时间复杂度为O(mn)

因此，总的时间复杂度为O((m+n)logn + mn)。

空间复杂度：使用了两个vector来存储桌子和客人的信息，所以空间复杂度为O(n+m)，其中n为桌子的数量，m为客人的数量