餐厅最少桌子安排问题的 C++ 实现

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; // 定义顾客结构体 struct Customer { int arrive_time; // 到达时间 int wait_time; // 最多等待时间 }; // 比较函数，用于优先队列，按离开时间排序 struct Compare { bool operator()(const int& a, const int& b) { return a > b; } }; int main() { int n, m; cin >> n >> m; // 输入顾客数量和用餐时间 vector<Customer> customers(n); for (int i = 0; i < n; ++i) { cin >> customers[i].arrive_time >> customers[i].wait_time; // 输入每位顾客的到达时间和最多等待时间 } priority_queue<int, vector<int>, Compare> tables; // 优先队列，存储每张桌子的空闲时间 int max_tables = 0; // 记录最多需要的桌子数 for (int i = 0; i < n; ++i) { // 检查当前空闲的桌子 while (!tables.empty() && tables.top() <= customers[i].arrive_time) { tables.pop(); } // 计算当前顾客离开的最晚时间 int leave_time = customers[i].arrive_time + customers[i].wait_time + m; // 如果没有空闲桌子，需要增加一张桌子 if (tables.size() == 0 || tables.top() > customers[i].arrive_time + customers[i].wait_time) { tables.push(leave_time); } else { // 有空闲桌子，更新该桌子的空闲时间 tables.pop(); tables.push(leave_time); } // 更新最多需要的桌子数 max_tables = max(max_tables, static_cast<int>(tables.size())); } cout << max_tables << endl; // 输出最少需要的桌子数 return 0; } ``` ### 代码解释： 1. **结构体 `Customer`**：用于存储每位顾客的到达时间和最多等待时间。 2. **优先队列 `tables`**：用于存储每张桌子的空闲时间，按空闲时间从小到大排序。 3. **遍历顾客**： - 对于每位顾客，检查当前空闲的桌子，如果有桌子在顾客到达时已经空闲，则将其从队列中移除。 - 计算当前顾客离开的最晚时间。 - 如果没有空闲桌子，需要增加一张桌子；否则，更新该桌子的空闲时间。 4. **更新最多需要的桌子数**：在遍历过程中，记录最多需要的桌子数。 5. **输出结果**：输出最少需要的桌子数。 ### 复杂度分析： - **时间复杂度**：$O(n log n)$，其中 $n$ 是顾客的数量。主要是优先队列的插入和删除操作的时间复杂度。 - **空间复杂度**：$O(n)$，主要是优先队列的空间开销。 ######[AI问答 | 729点数解答 | 2026-05-05 10:13:47]