CF2104B Move to the End

注意到，不论顺序如何改变，整个序列的总和是不变的。也就是说，要让后缀和最大，也就是让前缀和最小。

注意到，不论怎么交换，对 $a_{n-k+1}$ 来说，永远都会被“挤”出去。

于是找到最大值想法便呼之欲出了：我们首先计算出前缀最大值，将前 $n-k$ 个数的最大值交换到后 $k$ 个数中，而后利用前缀和计算出后 $k$ 个数之和。

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
int a[MAXN],mx[MAXN]={0};
long long sum[MAXN]={0};
int main()
{
    int T;
    scanf("%d",&T);
    while (T)
    {
        int n;
        long long ans=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
            mx[i]=max(mx[i-1],a[i]);
        }
        for (int i=n;i>=1;i--)
        {
            int change;
            change=mx[i];
            ans=sum[n]-sum[i-1]+change-a[i];
            printf("%lld ",ans);
        }
        printf("\n");
        T--;
    }
    return 0;
}