【题目来源】
https://www.luogu.com.cn/problem/P1223

【题目描述】
有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 Ti，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。

【输入格式】
第一行为一个整数 n。
第二行 n 个整数，第 i 个整数 Ti 表示第 i 个人的接水时间 Ti。

【输出格式】
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

【输入样例】
10
56 12 1 99 1000 234 33 55 99 812

【输出样例】
3 2 7 8 1 4 9 6 10 5
291.90

【说明/提示】
1≤n≤1000，1≤ti≤10^6，不保证 ti 不重复。

【算法分析】
● 经典排队打水问题参见：https://blog.csdn.net/hnjzsyjyj/article/details/129395368
● 本题可视为升级版的排队打水问题
设 x 和 y 是任意选取的两个人的打水时间，且 x<y。
那么针对 x 和 y 有两种排列情况：
（1）x 先于 y 打水，那么有总的等待时间：t1=x
（2）y 先于 x 打水，那么有总的等待时间：t2=y
显然，t1<t2。即：若将每人打水时间从小到大排序，可使总的等待时间最短。
推而广之，可得：当第 i（i≥1） 个人接水时，后面一共有 n - i 人等待，可得第 i 人接水时其他人的等待时间为第 i 人的接水时间乘以 n - i，即 。据前文证明，可知若将 n 个人的打水时间从小到大排序，可使总的等待时间最短。

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int maxn=1005;
struct Water {
    int id;
    int time;
} p[maxn];

bool up(Water a,Water b) {
    if(a.time!=b.time)
        return a.time<b.time;
    return a.id<b.id;
}

double ans;

int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>p[i].time;
        p[i].id=i;
    }
    sort(p+1,p+n+1,up);

    for(int i=1; i<=n; i++) ans+=(n-i)*p[i].time;
    for(int i=1; i<=n; i++) cout<<p[i].id<<" ";
    cout<<endl;

    ans/=n;
    printf("%.2f",ans);

    return 0;
}


/*
in:
10
56 12 1 99 1000 234 33 55 99 812

out:
3 2 7 8 1 4 9 6 10 5
291.90
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P1223
https://blog.csdn.net/hnjzsyjyj/article/details/129395368