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

ftggdnt

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

一、问题重述与分析

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

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

二、算法选择

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

详细步骤解析

• 数据预处理：
  
  
  • 桌子容量排序：使用multiset自动排序并允许重复
  • 客人排序：按消费金额降序排列
    
    
• 核心算法流程：
  
  
  • 遍历排序后的客人列表
  • 对每位客人，用lower_bound找到最小合适桌子
  • 如果找到，累加金额并移除该桌子
    
    
• 复杂度分析：
  
  
  • 排序：O(nlogn + mlogm)
  • 查找：O(mlogn)
  • 总体：O(nlogn + mlogm)
    
    

三、代码实现细节

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. #include <set>
   
5. using namespace std;
   
6. 
   
7. struct Guest {
   
8.     int b; // 人数
   
9.     int c; // 消费金额
   
10.     bool operator<(const Guest& other) const {
    
11.         return c > other.c; // 按金额降序排列
    
12.     }
    
13. };
    
14. 
    
15. int main() {
    
16.     ios::sync_with_stdio(false);
    
17.     cin.tie(nullptr);
    
18. 
    
19.     int n, m;
    
20.     cin >> n >> m;
    
21. 
    
22.     // 读取桌子容量并排序
    
23.     multiset<int> tables;
    
24.     for (int i = 0; i < n; ++i) {
    
25.         int a;
    
26.         cin >> a;
    
27.         tables.insert(a);
    
28.     }
    
29. 
    
30.     // 读取客人信息并排序(按金额降序)
    
31.     vector<Guest> guests(m);
    
32.     for (int i = 0; i < m; ++i) {
    
33.         cin >> guests[i].b >> guests[i].c;
    
34.     }
    
35.     sort(guests.begin(), guests.end());
    
36. 
    
37.     long long total = 0;
    
38.     for (const auto& guest : guests) {
    
39.         // 找到最小的大于等于人数的桌子
    
40.         auto it = tables.lower_bound(guest.b);
    
41.         if (it != tables.end()) {
    
42.             total += guest.c;
    
43.             tables.erase(it); // 该桌子被占用
    
44.         }
    
45.     }
    
46. 
    
47.     cout << total << endl;
    
48.     return 0;
    
49. }

复制代码

四、常见问题解答

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

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

五、扩展思考

• 如果允许拼桌，算法如何修改？
• 考虑翻台率因素后的优化方向
• 实时预约系统的算法调整
  
  

来源：牛客题解