乌拉乎餐厅问题：C++实现最少桌子安排方案

以下是解决该问题的C++代码： ```cpp #include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <queue> using namespace std; // 定义顾客结构体 struct Customer { int arriveTime; // 到达时间 int waitTime; // 最多等待时间 }; // 比较函数，用于优先队列，按离开时间从小到大排序 struct Compare { bool operator()(const int& a, const int& b) { return a > b; } }; int main() { ifstream fin("case.in"); // 打开输入文件 ofstream fout("case.out"); // 打开输出文件 int n, m; fin >> n >> m; // 读取顾客数量和用餐时间 vector<Customer> customers(n); for (int i = 0; i < n; ++i) { fin >> customers[i].arriveTime >> customers[i].waitTime; // 读取每个顾客的到达时间和最多等待时间 } priority_queue<int, vector<int>, Compare> tables; // 优先队列，存储每张桌子的空闲时间 int maxTables = 0; // 记录最大需要的桌子数 for (int i = 0; i < n; ++i) { int arrive = customers[i].arriveTime; int wait = customers[i].waitTime; // 移除已经空闲的桌子 while (!tables.empty() && tables.top() <= arrive) { tables.pop(); } // 检查顾客是否会离开 if (tables.size() > 0 && tables.top() > arrive + wait) { continue; // 顾客离开 } // 安排顾客用餐 tables.push(arrive + m); // 更新桌子的空闲时间 maxTables = max(maxTables, static_cast<int>(tables.size())); // 更新最大桌子数 } fout << maxTables << endl; // 输出结果到文件 fin.close(); // 关闭输入文件 fout.close(); // 关闭输出文件 return 0; } ``` ### 代码解释： 1. **结构体 `Customer`**：用于存储每个顾客的到达时间和最多等待时间。 2. **优先队列 `tables`**：用于存储每张桌子的空闲时间，按空闲时间从小到大排序。 3. **主循环**：遍历每个顾客，检查是否有空闲的桌子，如果有则安排顾客用餐，更新桌子的空闲时间，并更新最大桌子数。 4. **文件操作**：使用 `ifstream` 和 `ofstream` 分别进行输入和输出文件的操作。 ### 复杂度分析： - **时间复杂度**：$O(n log n)$，主要是优先队列的操作。 - **空间复杂度**：$O(n)$，主要是优先队列的空间。 ######[AI问答 | 684点数解答 | 2026-04-21 19:41:58]