A、Sum

吐槽

再经过"YE5"和"N0"后又一次被牛客恶心到辣，为什么是对1e7+7取模啊喂！

前置知识：排序+贪心

问题解析

每次我们可以合并至少两个数，并获得等同于他们之和的分数总和。

那么对于贪心来说，我们可以先对所有数进行降序排序（大的在前面，小的在后面）。

每次合并最大的两个数即可，而因为每次合并后数组最大的两个数肯定是原数组最大的数和当前合并产生的数。

我们可以用一个变量sum记录每次合并后的值，下一次合并只要把数组剩下的最大的值加到sum上，就算完成合并了，每次合并后把sum加到我们的结果上（我这里用一个变量res来存储结果）。

我们就持续合并，直到数组只剩下一个数，或者合并后sum会小于0为止，最后输出结果（res）。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6+50, MOD = 1e7+7;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}

void solve()
{
    int n;
    cin >> n;
    vector<int>v(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    sort(v.begin(), v.end(), greater<int>());
    int res = 0, sum = v[0];
    for (int i = 1; i < n; i++)
    {
        if (sum + v[i] < 0)break;
        sum += v[i];
        res = (res + sum) % MOD;
    }
    cout << res<< endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}