题解 | #显生之宙#

1. 问题分析

首先，分析单次操作对数列总和的影响：

• 操作描述：选定一个数 ，将其加到数列中至少一个其他数上，然后移除 。
• 数学表达：设当前选中的数为 ，选中的目标集合为 （其中 ）。
  • 操作后，这些数变为 。
  • 数列的总和变化量 。

目标：最小化最后的剩余值。 由于最后只会剩下一个数，这个数的大小等于 初始总和 + 历次操作产生的 之和。

2. 算法

为了使最终结果最小，我们需要让每一次操作的 尽量小：

1. 当 时： 我们要让 尽可能小（即绝对值尽可能大且为负）。由于 是负数，应使 达到最大值。在有 个数时，最大可取权重 。这意味着将当前的负数 加到此时数列中所有其他的数上。
2. 当 时： 我们要让 尽可能小。由于 且 ，则 的最小值为 ，此时取 。这意味着将正数 只加到一个其他的数上，此时总和不增加。

关键洞察：

• 负数可以作为“减法器”，通过给多个数加负数来大幅降低总和。
• 正数无法降低总和，只能维持总和不变。
• 为了最大限度利用负数，我们应该先处理最负的数，因为它能产生的削减效果最强，并且会被后续的负数进一步累积。

3. 代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        ll S = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            S += a[i];
        }
        sort(a.begin(), a.end());
        ll offset = 0;
        for (int i = 0; i < n - 1; i++) {
            ll x = a[i] + offset;
            if (x < 0) {
                S += (ll)(n - i - 2) * x;
                offset += x;
            } else {
                break;
            }
        }
        cout << S << endl;
    }
}