牛客12650题解析：基于贪心算法的桌子与客人匹配问题

一、题目解读

牛客12650题要求处理一个资源分配问题：给定n张不同容量的桌子与m个携带消费金额的客人，客人需匹配到可容纳人数的桌子，目标是最大化所有匹配客人的总消费金额。题目本质是约束条件下的优化问题，需平衡桌子容量与客人需求的匹配效率。

二、解题思路

1. 贪心策略核心：优先安排高消费金额的客人，确保“价值最大化”的匹配。

2. 数据结构选择：

    桌子容量存入multiset（支持自动排序与快速查找），便于动态删除已占用桌子。

    客人信息用vector存储，按消费金额降序排序，确保优先处理高价值客人。

3. 关键操作：通过lower_bound定位首个满足容量要求的桌子，实现O(logn)查找效率，避免暴力遍历。

三、解题步骤

1. 输入处理：

    读取桌子容量并存入multiset，自动升序排列。

    读取客人信息（人数与消费金额），存入vector后排序（金额降序）。

2. 匹配逻辑：

    遍历客人列表，对每个客人调用tables.lower_bound(人数)查找合适桌子。

    若找到桌子，累加消费金额并删除该桌子（避免重复使用）。

3. 输出结果：最终累计的消费总额即为最优解。

四、代码与注释

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

// 客人结构体（按消费金额降序排序）
struct Guest {
    int b; // 人数
    int c; // 消费金额
    bool operator<(const Guest& other) const {
        return c > other.c; // 自定义排序规则：金额降序
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入

    int n, m; // 桌子数量、客人数量
    cin >> n >> m;

    // 桌子容量存入multiset（自动排序）
    multiset<int> tables;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        tables.insert(a);
    }

    // 客人信息读取与排序
    vector<Guest> guests(m);
    for (int i = 0; i < m; ++i) {
        cin >> guests[i].b >> guests[i].c;
    }
    sort(guests.begin(), guests.end()); // 按消费金额降序排列

    long long total = 0; // 累计消费金额
    for (const auto& guest : guests) {
        // 查找首个满足人数的桌子（O(logn)）
        auto it = tables.lower_bound(guest.b);
        if (it!= tables.end()) {
            total += guest.c;
            tables.erase(it); // 删除已占用桌子
        }
    }

    cout << total << endl;
    return 0;
}

五、总结

本解法通过“贪心+数据结构优化”实现高效解题：

● 排序与lower_bound的结合避免了复杂匹配搜索，时间复杂度O(mlogn)。

● 动态删除占用桌子确保解的唯一性，符合题目约束。

● 代码结构清晰，注释明确，适用于算法面试与工程实践。