使用 C++ 计算餐厅最少所需桌子数以满足所有顾客用餐

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> #include <algorithm> // 定义顾客结构体，包含到达时间、最大等待时间和离开时间 struct Customer { int arrivalTime; int waitTime; int leaveTime; }; // 比较函数，按照顾客的到达时间进行排序 bool compareByArrival(const Customer& a, const Customer& b) { return a.arrivalTime < b.arrivalTime; } // 计算最少需要的桌子数 int minTablesRequired(const std::vector<Customer>& customers, int m) { int n = customers.size(); std::vector<int> tableEndTimes; // 存储每张桌子的结束使用时间 for (const auto& customer : customers) { int availableTable = -1; // 遍历所有桌子，找到最早结束使用且能满足当前顾客等待时间的桌子 for (int i = 0; i < tableEndTimes.size(); ++i) { if (tableEndTimes[i] <= customer.arrivalTime) { availableTable = i; break; } } if (availableTable != -1) { // 如果找到可用桌子，更新该桌子的结束使用时间 tableEndTimes[availableTable] = customer.arrivalTime + m; } else { // 如果没有可用桌子，添加一张新桌子 tableEndTimes.push_back(customer.arrivalTime + m); } } return tableEndTimes.size(); } int main() { int n, m; std::cout << "请输入顾客的数量 n 和用餐时间 m: "; std::cin >> n >> m; std::vector<Customer> customers(n); for (int i = 0; i < n; ++i) { std::cout << "请输入第 " << i + 1 << " 名顾客的到达时间和最大等待时间: "; std::cin >> customers[i].arrivalTime >> customers[i].waitTime; customers[i].leaveTime = customers[i].arrivalTime + customers[i].waitTime; } // 按照顾客的到达时间进行排序 std::sort(customers.begin(), customers.end(), compareByArrival); int result = minTablesRequired(customers, m); std::cout << "餐厅至少需要安排 " << result << " 张桌子才能让所有顾客都吃上饭。" << std::endl; return 0; } ``` ### 代码解释： 1. **结构体 `Customer`**：用于存储每个顾客的到达时间、最大等待时间和离开时间。 2. **比较函数 `compareByArrival`**：用于对顾客按照到达时间进行排序。 3. **函数 `minTablesRequired`**：计算最少需要的桌子数。遍历每个顾客，尝试找到最早结束使用且能满足当前顾客等待时间的桌子。如果找到，则更新该桌子的结束使用时间；否则，添加一张新桌子。 4. **主函数 `main`**：读取输入的顾客数量、用餐时间和每个顾客的到达时间和最大等待时间，调用 `minTablesRequired` 函数计算最少需要的桌子数，并输出结果。 ### 复杂度分析： - **时间复杂度**：排序的时间复杂度为 $O(n log n)$，遍历每个顾客的时间复杂度为 $O(n)$，因此总的时间复杂度为 $O(n log n)$。 - **空间复杂度**：主要用于存储每张桌子的结束使用时间，空间复杂度为 $O(n)$。 ######[AI问答 | 841点数解答 | 2026-05-05 10:09:23]