贪心+前缀和

熟悉的题目，这不就是雨巨直播课讲的接水问题吗，直接贪心求前缀和就ok

方法一：

1.对于每个人等待的时间求和我们可以知道对于t1已经求和n-1次，t2求和n-2次，所以按照贪心的思想我们就把等待时间小的排在前面
2.对于排好序的序列，我们只需要求其前缀和然后相加求平均数就可以啦，由于题目要求我们需要保留两位有效数字

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main()
{
    int t, n;
    scanf("%d", &t);
    double ans, sum;
    while (t--)
    {
        sum = 0, ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        for (int i = 1; i < n; ++i)
        {
            ans += a[i];
            sum += ans;
        }
        printf("%.2lf\n", sum / n);
    }
}

方法二：

经过上面的分析，我们知道了另外一些信息，时间t的下标与求和的次数相加就是n，所以我们可以通过这个方向用另外一种简单方法求解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main()
{
    int t, n;
    scanf("%d", &t);
    double ans, sum;
    while (t--)
    {
        sum = 0, ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        for (int i = 1; i < n; ++i)
            sum += a[i] * (n - i);
        printf("%.2lf\n", sum / n);
    }
}