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

14小时前牛客题解25

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

一、问题重述与分析

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

不允许拼桌
每批客人必须全部安排在一张桌子
桌子容量必须≥客人数

二、算法选择

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

详细步骤解析

数据预处理：

桌子容量排序：使用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;
}