题目描述:
白垩色的王子给了你一个由 n 个数组成的数列，并告诉你，你需要执行 n-1次如下操作：
选定一个数列中的数 x，再选择数列中的至少一个其他数，然后让这些数都加上 x，再将 x 移除出这个数列。
经 n-1 次操作过后，数列中最后只会剩下一个数。白垩色的王子希望你告诉他，最后剩下的那个数最小是多少。题目保证最后输出的答案的绝对值 <=4*10e18。
**
思路分析
:我们先想一想,如果全都是正数,我们只能让一个数加最多加一个数,这样才能使得最后剩下的那一个数是最小的,而且我们要保证每次加过来的数是最小的的如果每次加来的是最大的数,相当于变相的加了很多次大的数这就导致最后的剩下的数不是我们需要的了,如果有负数存在我们应该让这个负数去加每一个数,这样使得最后的数是最小的:**
*
温馨提示:*
我们在计算所有负数加到1其他数上面的过程里面,如果用暴力的话肯定会超时,所以我们应该想一个优化的方式,因为负数是加到每一个数,这一个过程是累加的,因此我们不需要一个一个数去加,我们可以把所有负数先加在一起,用now来维护,防止超时
代码如下
#include<iostream>
#include<algorithm>
using namespace std;
int T;
long long n;
long long a[500005];
int main()
{
cin>>T;//循环次数
while(T--)
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
sort(a + 1, a + n + 1);排序每次加最小的
long long ans = 0, now = 0,sum=0;
for (int i = 1; i <= n; i ++)
{
a[i] += now ;
if (a[i] < 0) now += a[i];
//这一步非常关键,把所有负数放一起
//省的加好几次
else ans += a[i];
}
if (a[n] < 0) ans = a[n];
///特判一下,因为上面else是a[i]大于0的情况才有,
//所以如果a[]里面全是负数那么ans将不会被更新了
cout << ans << '\n';
}