C++ 最小平均等待时间：优化井前排队打水顺序 - 无需使用 vector

思路：\n首先，根据题目的要求，我们需要找到一种排列顺序，使得n个人的平均等待时间最小。那么我们可以使用贪心的思想来解决这个问题。\n\n具体步骤如下：\n1. 首先，读取输入的n和每个人的打水时间Ti。\n2. 构建一个包含n个元素的数组order，用来保存每个人的排队顺序。\n3. 对于每个人，将其打水时间和对应的编号存入一个pair中，并将这些pair放入一个vector中。\n4. 对vector进行排序，按照打水时间从小到大排列。当打水时间相同时，按照输入顺序排列。\n5. 遍历排序后的vector，将每个pair中的编号依次填入order数组中。\n6. 计算平均等待时间，即将每个人的打水时间累加起来，除以n。\n7. 输出order数组和平均等待时间。\n\n代码实现如下：\n\ncpp\n#include <iostream>\n#include <algorithm>\nusing namespace std;\n\nint main() {\n int n;\n cin >> n;\n\n int order[1000]; // 使用数组代替 vector\n int time[1000]; // 记录每个人的打水时间\n for (int i = 0; i < n; i++) {\n cin >> time[i]; \n }\n\n // 使用冒泡排序对打水时间进行排序\n for (int i = 0; i < n - 1; i++) {\n for (int j = 0; j < n - i - 1; j++) {\n if (time[j] > time[j + 1]) {\n swap(time[j], time[j + 1]);\n swap(order[j], order[j + 1]);\n }\n }\n }\n\n // 初始化顺序数组\n for (int i = 0; i < n; i++) {\n order[i] = i + 1;\n }\n\n double sum = 0;\n for (int i = 0; i < n; i++) {\n sum += time[i] * (n - i - 1);\n }\n\n double avg_time = sum / n;\n\n for (int i = 0; i < n; i++) {\n cout << order[i] << " ";\n }\n cout << endl;\n cout << fixed << setprecision(2) << avg_time << endl;\n\n return 0;\n}\n\n\n复杂度分析：\n1. 排序的时间复杂度为O(n^2)。\n2. 遍历数组的时间复杂度为O(n)。\n3. 计算平均等待时间的时间复杂度为O(n)。\n因此，总的时间复杂度为O(n^2)。\n\n注意：\n本代码使用了冒泡排序来代替 vector 进行排序，降低了空间复杂度，但时间复杂度略微上升。在实际应用中，可以根据具体情况选择合适的排序算法。