题解 | #显生之宙#

显生之宙

https://ac.nowcoder.com/acm/problem/267923

本蒟蒻想方设法地尝试了做了很久，总算是做出来了（哭）（本来想用优先队列做的，后面通过率只有90%）（悲）

————————————————————————————————————————————————————

按照题目的意思，有n个数，进行n-1次操作，最后留下一个数

首先是开数组并对数组内的元素输入。

根据题目的意思，可以选择数组里面任意一个数（x)，再对至少一个其他数 把这个(x)加给它们 ，再把这个x移出列

题目所要求的是，最后留下来的数要尽可能得小，这说明最后那个数相加过的x最好是 越多负数越好，越少正数越好

由此我们可以观察到两点：

{

如果x是负数，那么这个x应该给数组内所有的x都提供贡献，让它们全部变小；

如果x是正数，那么这个x应该给数组内某个正数提供贡献；（因为如果都提供的话，这个值变得更大）

}

同时想到某些数（比如0）加上负数之后会变成负数，我们要让这种情况发生得越多越好

所以我们对数组进行从小到大的排列，让所有的负数先给数组内的所有的值提供贡献（也算是尝试让某些个非负数变成负数)

我定义了个sum变量和minus变量：

{

minus变量用于存放至今为止所有的负数提供过的贡献；

sum变量是以数组最后的值为基准发生过的变化的总值；

}

在每一次循环中，用 temp存储num[i]，代表当前数字的值，再用temp减去minus代表这个值被minus贡献过后是多少。

如果temp被minus贡献过后的值小于0，那么这个temp的值我们就贡献给所有值

反之如果这个temp是大于等于0，那么这个temp我们就只贡献给最后的最大值

所以作为sum来说（最后的最大值来说），无论怎样这个值都是必须加的

最后我们再把我们的最大值给加进去，就得到结果

//是的我知道这很抽象，但是本蒟蒻在一开始是不仅加上最大值而且还加上了minus，结果就不对了

//我也不知道怎么解释，但是我抱着：”sum本身是以最大值为基准，最后加上最大值也没问题吧“的心态试了一下就过了

//不知道有没有大佬懂具体是怎么说，orz orz orz 给跪了

模拟案例1的第二组的话就是

-1 8 -2 0变成 -2 -1 0 8

temp=-2+0=-2小于0，minus=0+(-2)=-2，sum=0+(-2)=-2

temp=-1+(-2)=-3小于0，minus=-2+(-3)=-5,sum=-2+(-3)=-5

temp=0+(-5)=-5小于0,minus=-5+(-5)=-10，sum=-5+(-5)=-10

sum=sum+最后值（8）=-10+8=-2

不知道好不好懂，也不知道题解写得好不好…………总体来说也是做完题目思考完，写个题解不仅帮别人理解也加深一些印象和理解吧…………

蒟蒻走了，orz

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        
        vector<long long>num(n);
        
        for(int i=0;i<n;i++)
        {
            cin>>num[i];
        }
        
        long long sum=0;
        long long minus=0;
        
        sort(num.begin(),num.end());
        
        for(int i=0;i<n-1;i++)
        {
            long long temp=num[i];
            
            temp=temp+minus;
            
            sum=sum+temp;
 
            if(temp<0)
            {
                minus+=temp;
            }
        }
        
        sum=sum+num[num.size()-1];
        cout<<sum<<endl;
        
    }
}