牛客网4812题：从贪心到二分，餐馆安排最优算法解析

牛客网4812题要解决餐馆经营问题，想象你是一家热门餐馆的经理，每天需要安排大量客人入座。如何在不拼桌的情况下，让餐馆获得最大收益？

一、问题重述与分析

我们需要处理n张桌子(容量各不相同)和m批客人(人数和消费金额不同)，目标是通过合理安排使总消费金额最大化。关键约束：

1. 不允许拼桌

2. 每批客人必须全部安排在一张桌子

3. 桌子容量必须≥客人数

二、算法选择

贪心策略：优先安排单位人数消费高的客人 二分查找：快速找到合适桌子

详细步骤解析

1. 数据预处理：

• 桌子容量排序：使用multiset自动排序并允许重复

• 客人排序：按消费金额降序排列

核心算法流程：

• 遍历排序后的客人列表

• 对每位客人，用lower_bound找到最小合适桌子

• 如果找到，累加金额并移除该桌子

复杂度分析：

• 排序：O(nlogn + mlogm)

• 查找：O(mlogn)

• 总体：O(nlogn + mlogm)

三、代码实现细节

#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<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) {
        // 找到最小的大于等于人数的桌子
        auto it = tables.lower_bound(guest.b);
        if (it != tables.end()) {
            total += guest.c;
            tables.erase(it); // 该桌子被占用
        }
    }

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

四、常见问题解答

Q：为什么不用动态规划？ A：数据规模太大(5e4)，DP复杂度不可接受

Q：如何处理相同消费金额的客人？ A：任意顺序处理均可，不影响最终结果

五、扩展思考

1. 如果允许拼桌，算法如何修改？

2. 考虑翻台率因素后的优化方向

3. 实时预约系统的算法调整

来源：牛客题解