C++ 最小平均等待时间排队问题（不使用 vector 头文件）

问题描述

在一个小村子里，生活着 n 户人家。由于村里只有一口井，所以他们每天早上一户人家派一个人在这一口井前排队打水。由于每家的水桶大小不同，所以每个人的打水时间也不同。假如每个人打水的时间为 Ti，请你编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。

输入描述

共两行，第一行为 n；第二行分别表示第 1 个人到第 n 个人每人的打水时间 Ti，每个数据之间有 1 个空格。

输出描述

共两行，第一行为一种排队顺序，即 1 到 n 的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

样例 1

输入

10
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
291.90

提示

n <= 1000
Ti <= 1e6，不保证 Ti 不重复
当 Ti 重复时，按照输入顺序即可（sort 是可以的）

算法分析

首先，我们可以使用一个数组来存储每个人的打水时间 Ti，然后根据题目要求找出平均等待时间最小的排队顺序。

为了计算平均等待时间，我们需要知道每个人等待的时间。假设第 i 个人的打水时间为 Ti，那么他前面有 i-1 个人需要等待，他自己还需要等待的时间为 (Ti * (n-i))。因此，第 i 个人的总等待时间为 (Ti * (n-i)) + (Ti * (n-i-1)) + ... + (Ti * 1)。

为了求出所有人的总等待时间，我们可以先将数组按照打水时间 Ti 从小到大排序。然后，遍历排序后的数组，依次计算每个人的总等待时间，并累加到总等待时间中。

最后，我们还需要输出一种排列顺序。由于题目要求按照输入顺序排列，我们可以在排序数组时，同时记录每个人的原始下标。然后根据原始下标的顺序输出排列顺序。

C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

int main() {
    int n;
    cin >> n;
    
    int T[n];
    for (int i = 0; i < n; i++) {
        cin >> T[i];
    }
    
    pair<int, int> arr[n];
    for (int i = 0; i < n; i++) {
        arr[i] = make_pair(T[i], i+1);
    }
    
    sort(arr, arr+n, cmp);
    
    double total_wait_time = 0;
    for (int i = 0; i < n; i++) {
        total_wait_time += arr[i].first * (n - i);
    }
    
    cout << arr[0].second;
    for (int i = 1; i < n; i++) {
        cout << ' ' << arr[i].second;
    }
    cout << endl;
    
    double avg_wait_time = total_wait_time / n;
    printf("%.2f\n", avg_wait_time);
    
    return 0;
}

该程序首先读取输入的 n 和每个人的打水时间 Ti，然后使用一个 pair 数组 arr 来存储每个人的打水时间和原始下标。然后，将数组按照打水时间从小到大排序，同时按照原始下标记录排列顺序。接下来，计算总等待时间并输出排列顺序和平均等待时间。

注意，我们使用了 printf 函数来输出平均等待时间，并限制输出的小数点后两位。

代码解释

使用 pair 结构存储每个人的打水时间和原始下标，方便排序后还原顺序。
使用 sort 函数对 pair 数组进行排序，比较函数 cmp 用于按照打水时间进行从小到大排序。
遍历排序后的数组，计算每个人的总等待时间，并累加到 total_wait_time 中。
按照排序后的 pair 数组的原始下标输出排列顺序。
计算平均等待时间 avg_wait_time 并使用 printf 函数输出，保留两位小数。

总结

通过使用 pair 结构，并结合排序和计算总等待时间的方法，我们可以有效地找到排队顺序，使得所有人的平均等待时间最小。代码简洁易懂，并能准确地计算出结果。