CF1805F1. Survival of the Weakest (easy version)

题意

给定一个数组 $a_1,a_2…,a_n$，定义 $F(a_1,a_2,…,a_n)$ 为如下的函数：

$F(a_1,a_2,…,a_n)$ 将会在 $\forall 1\leq i < j \leq n$ 中，选取最小的 $n-1$ 个 $a_i+a_j$，然后组成一个新的sort好的数组。

例如 $F(1,2,5,7) = [1+2,1+5,2+5] = [3,6,7]$。

给定 $a_1,a_2,…,a_n$，求 $F^{n-1}(a_1,a_2,…,a_n)$ 的值（即对这个数组进行 $n-1$ 次操作）。

其中，$2 \leq n \leq 3000, a_i \in [0,10^9]$，答案对 $10^9+7$ 取模。

题解

我们在下文假设 $a_1,a_2,…,a_n$ 始终为 sort 好的。

由于 $n \leq 3000$，考虑直接暴力求 $F$。

我们注意到，如果 $i<j$ 且 $a_i+a_{j+1}$ 被 $F$ 选中了，那么 $a_i+a_j$ 也一定会被更早选中（因为sorted）。

所以对于所有的pair的左端点 $i$，我们只需要考虑当前尚未选中的右端点 $j$，如果 $j$ 被选中了那么才考虑 $j+1$ 作为右端点。

于是我们开一个 pq，先存进 $(a_1,a_2), (a_2,a_3), …, (a_{n-1},a_n)$。

当 $(a_i,a_j)$ 被 pop 出来加入下一轮后，push进 $(a_i,a_{j+1})$。

这样就可以在 $O(n\log n)$ 内进行一轮 $F$ 了。

但是，答案对 $10^9+7$ 取模，我们显然不能在求解 $F$ 的过程中取模，因为这会破坏数字之间的大小关系，怎么办？

我们发现 $F(a_1-x,a_2-x,…,a_n-x) = F(a_1,a_2,…,a_n) - 2^{n-1}x$，所以每一轮我们先减掉当前数组中的最小值，给答案加上即可。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;

Z p2[maxn], ans = 0;
struct Node {
    ll val;
    int i, j;
    bool operator<(const Node& other) const {
        return val > other.val;
    }
};
vector<ll> f(vector<ll>& vec) {
    priority_queue<Node> pq;
    int n = vec.size();
    ll mn = 1e18;
    for (int i = 0; i < n; i++) {
        mn = min(mn, vec[i]);
    }
    for (int i = 0; i < n; i++) vec[i] -= mn;
    ans += p2[n-1] * mn;

    vector<ll> res;
    for (int i = 0; i < n-1; i++) {
        pq.push({vec[i] + vec[i+1], i, i+1});
    }
    for (int i = 1; i < n; i++) {
        auto [val, l, r] = pq.top();
        pq.pop();
        res.push_back(val);
        if (r + 1 < n) {
            pq.push({vec[l] + vec[r+1], l, r+1});
        }
    }
    return res;
}

int n;
int main() {
    cin >> n;
    p2[0] = 1;
    for (int i = 1; i <= n; i++) p2[i] = p2[i-1] * 2;
    vector<ll> vec;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        vec.push_back(x);
    }
    sort(vec.begin(), vec.end());
    for (int t = 1; t < n; t++) {
        vec = f(vec);
    }
    cout << ans + vec[0] << "\n";
}