题解：CF1805F1 Survival of the Weakest (easy version)

· · 题解

首先考虑最小的 n - 1 个 a_i + a_j，怎么做，这是一个很经典的问题，用堆维护。先将 a 数组排序，对于每个 i，先令 pos_i = i + 1，我们先每个将 a_i + a_{pos_i} 压到小根堆里，接着每次取堆顶，若当前的值是由 a_i + a_{pos_i} 得到的，那么我们将 pos_i 往后移，即 pos_i = pos_i+ 1，接着再将将 a_i + a_{pos_i} 压到小根堆里，这样做 n - 1 次就找到了最小的 n - 1 个 a_i + a_j，因为 a 是不降的，所以从前往后找必然是先找到更小的值，再是更大的值。

这样单次是 O(n \times \log{n}) 的，因为 n \le 3000，所以可以直接做 n - 1 次得出答案。

但是，最坏情况下做一次值翻倍，做 3000 次显然值是非常大的。我们可能会想到离散化，但是这样元素之间的差值会被改变，无法正确进行上述用堆求最小值的过程。但是，我们又会发现，我们只需要知道元素之间的差值，所以我们可以将 a 数组中的每个数字都减去 a_{min}，这样就可以保证数值不会过大。

接着我们在计算每轮减去的 a_{min} 对答案的贡献，一轮操作后，F(a_{min} + b_1, a_{min} + b_2, \cdots, a_{min} + b_k) 变为 F(2 \times a_{min} + c_1, 2 \times a_{min} + c_2, \cdots, 2 \times a_{min} + c_{k - 1})，a_{min} 的贡献翻倍，那么对于第 i 的操作得到的 a_{min} 对答案的贡献就是 a_{min} \times 2 ^ {n - i - 1}。初始情况算作第 0 轮。

Code

#include <bits/stdc++.h>
#define Pii pair <int, int>
#define int long long
using namespace std;
const int N = 3e3 + 5, Mod = 1e9 + 7;
int n, pos[N], pw[N];
vector <int> arr, Fmin;
priority_queue < Pii, vector <Pii>, greater <Pii> > q;

vector <int> solve(vector <int> arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) pos[i] = i + 1, q.emplace(arr[i] + arr[i + 1], i);
    vector <int> ary;
    while(q.size()) {
        Pii u = q.top(); q.pop();
        ary.push_back(u.first);
        if(ary.size() == n - 1) break;
        int i = u.second; ++ pos[i];
        if(pos[i] < n) q.emplace(arr[i] + arr[pos[i]], i);
    }
    Fmin.push_back(ary.front());
    for (int& x : ary) x -= Fmin.back();
    while(q.size()) q.pop();
    return ary;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n, arr.resize(n);
    for (int& x : arr) cin >> x;
    sort(arr.begin(), arr.end());
    Fmin.push_back(arr.front());
    for (int& x : arr) x -= Fmin.back();
    for (int i = 1; i < n; ++i) arr = solve(arr);
    int ans = 0; pw[0] = 1;
    for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * 2 % Mod;
    for (int i = 0; i < Fmin.size(); ++i) ans = (ans + pw[n - i - 1] * Fmin[i] % Mod) % Mod;
    cout << ans << '\n';
    return 0;
}