C++且不使用vector头文件完成：在一个小村子里生活着n户人家。由于村里只有一口井所以他们每天早上一户人家派一个人在这一口井前排队打水。由于每家的水桶大小不同所以每个人的打水时间也不同。假如每个人打水的时间为Ti请你编程找出这n个人排队的一种顺序使得n个人的平均等待时间最小。输入描述共两行第一行为n；第二行分别表示第 1 个人到第n个人每人的打水时间Ti每个数据之间有 1 个空格。输出描述共两

解题思路： 首先，根据题意，我们需要找出n个人排队的一种顺序，使得n个人的平均等待时间最小。由于每个人的打水时间不同，我们可以按照打水时间从小到大的顺序对人进行排序。

首先，我们需要定义一个结构体Person，用于保存每个人的序号和打水时间。然后，我们根据打水时间对人进行排序，可以使用冒泡排序或者快速排序等算法。

排序完成后，我们将得到一个按照打水时间从小到大排列的人的序列。我们可以根据这个序列计算出每个人的等待时间，并求出平均等待时间。

具体实现步骤如下：

1. 定义结构体Person，包含成员变量index（人的序号）和time（打水时间）。
2. 输入n和n个人的打水时间。
3. 创建一个Person类型的数组people，大小为n，用于存储每个人的信息。
4. 将输入的打水时间存入people数组，并为每个人设置序号。
5. 对people数组根据打水时间进行排序，可以使用冒泡排序或者快速排序等算法。
6. 输出排序后的人的序号。
7. 计算每个人的等待时间，并求出平均等待时间。
8. 输出平均等待时间，保留两位小数。

C++代码实现如下：

#include #include using namespace std;

struct Person { int index; int time; };

bool cmp(Person a, Person b) { return a.time < b.time; }

int main() { int n; cin >> n;

Person people[n];
for (int i = 0; i < n; i++) {
    cin >> people[i].time;
    people[i].index = i + 1;
}

sort(people, people + n, cmp);

for (int i = 0; i < n; i++) {
    cout << people[i].index << " ";
}
cout << endl;

double sum = 0;
for (int i = 0; i < n; i++) {
    sum += (n - i - 1) * people[i].time;
}
double average = sum / n;

cout.precision(2);
cout << fixed << average << endl;

return 0;

}

时间复杂度分析： 排序的时间复杂度为O(nlogn)，计算平均等待时间的时间复杂度为O(n)，所以总的时间复杂度为O(nlogn)