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

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; // 定义顾客结构体，包含到达时间和最多排队时间 struct Customer { int arrival; int wait; }; int main() { int n, m; cin >> n >> m; vector<Customer> customers(n); // 读取每个顾客的到达时间和最多排队时间 for (int i = 0; i < n; ++i) { cin >> customers[i].arrival >> customers[i].wait; } // 优先队列，存储每张桌子的空闲时间 priority_queue<int, vector<int>, greater<int>> tables; int maxTables = 0; for (int i = 0; i < n; ++i) { // 移除已经空闲的桌子 while (!tables.empty() && tables.top() <= customers[i].arrival) { tables.pop(); } // 检查当前顾客是否可以等待到有桌子空闲 int availableTime = 0; if (!tables.empty()) { availableTime = tables.top(); } if (availableTime == 0 || availableTime - customers[i].arrival <= customers[i].wait) { // 如果可以等待，安排桌子 tables.push(max(availableTime, customers[i].arrival) + m); } // 更新最大桌子数 maxTables = max(maxTables, static_cast<int>(tables.size())); } cout << maxTables << endl; return 0; } ``` ### 代码解释 1. **结构体 `Customer`**：用于存储每个顾客的到达时间和最多排队时间。 2. **优先队列 `tables`**：用于存储每张桌子的空闲时间，使用小顶堆实现，每次取出最早空闲的桌子。 3. **遍历顾客**： - 移除已经空闲的桌子。 - 检查当前顾客是否可以等待到有桌子空闲。 - 如果可以等待，安排桌子并更新桌子的空闲时间。 - 更新最大桌子数。 4. **输出结果**：输出满足所有顾客用餐的最少桌子数。 ### 复杂度分析 - **时间复杂度**：$O(n \log n)$，其中 $n$ 是顾客的数量。每次操作优先队列的时间复杂度为 $O(\log n)$，共进行 $n$ 次操作。 - **空间复杂度**：$O(n)$，主要用于存储优先队列。 ######[AI问答 | 604点数解答 | 2026-05-05 12:01:33]