C++ 实现最优排队打水方案（无 vector 头文件）

这道题可以使用贪心算法来解决。贪心算法的思路是，尽量让打水时间短的人先打水，这样可以减少等待时间。\n\n首先，我们需要定义一个结构体来表示每个人的信息，包括编号和打水时间。然后，我们将这些人按照打水时间从小到大排序。\n\n接下来，我们需要计算每个人的等待时间。由于每个人的打水时间不同，所以等待时间也不同。我们可以使用一个变量来表示当前时间，初始值为0。然后，遍历排序后的人的列表，对于每个人，计算他的等待时间，并更新当前时间。\n\n最后，我们将排序后的人的编号输出，同时计算平均等待时间。\n\n以下是完整的 C++ 代码实现：\n\ncpp\n#include <iostream>\n#include <algorithm>\nusing namespace std;\n\nstruct Person {\n int id;\n int time;\n};\n\nbool cmp(const Person& p1, const Person& p2) {\n return p1.time < p2.time;\n}\n\nint main() {\n int n;\n cin >> n;\n \n Person people[n];\n for (int i = 0; i < n; i++) {\n cin >> people[i].time;\n people[i].id = i + 1;\n }\n \n sort(people, people + n, cmp);\n \n int currentTime = 0;\n double totalWaitTime = 0;\n for (int i = 0; i < n; i++) {\n int waitTime = currentTime;\n currentTime += people[i].time;\n totalWaitTime += waitTime;\n }\n \n for (int i = 0; i < n; i++) {\n cout << people[i].id << " ";\n }\n cout << endl;\n \n cout << fixed;\n cout.precision(2);\n cout << totalWaitTime / n << endl;\n \n return 0;\n}\n\n\n时间复杂度分析：排序的时间复杂度为O(nlogn)，遍历列表的时间复杂度为O(n)，所以总的时间复杂度为O(nlogn)。空间复杂度为O(n)，用来存储人的信息。