[CF1805F1] Survival of the Weakest (easy version) 题解

· · 题解

提供一种只能过 easy version 的解法。

对于 n \leq 3000，考虑暴力合并 F 数组，每次保留前 k 小的和值 a_i+a_j，可以使用堆贪心：对于一个有序数组 a，a_i+a_j\leq a_i+a_{j+1}，用堆维护 a_i+a_j 的最小值，开始时将 n 个二元组 (i,1) 放入堆中，每次拿出最小值之后将二元组 (i,j) 改为 (i,j+1) 后再放去，这样可以在 (n+k)\log k 的时间复杂度下完成选择前 k 大的和值这一操作。

但是还有一个问题：F 数组中的数字增长速度太快了。使用高精度的话时间复杂度又将变得不可接受。而如果相对大小不改变，选择的数也不会被改变，所以我们考虑再每一次迭代后，将 F 中的每个元素都减去 F 数组中的最小值 F_1，而 F_1 在对最终答案产生贡献之前，还会被合并若干轮，每一轮的 F_1 都将会被倍增（因为无论怎么合并元素，其中都是默认含有 F_1 的），也就是说，对于第 i 轮合并后被减掉的 F_1，还会被合并 n-i-1 轮，所以其对答案的贡献就是 F_1\times 2^{n-i-1}，于是只要在每轮迭代完成后将所有数减去 F_1 并累加到贡献上就可以了，时间复杂度 \Theta(n^2\log n)。

接下来证明为什么这样做之后数列中的元素就不会超过 int 范围：对于一个长度为 k 的数组 F，产生的后续数组 F' 中最小的元素显然是 F_1+F_2，而最大的元素 F'_{k-1} \leq F_1+F_{k-1}。所以在减去最小值之后，数组的最大值 F'_{k-1}\leq(F_1+F_{k-1})-(F_1+F_2) = F_{k-1}-F_2 \leq F_k，也就是 F 数组的最大值在每次迭代之后单调不升，因此保证了无论何时 F 数组中的所有的元素不会超过 10^9。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000 + 5;
const int M = 1e9 + 7;
int a[N],b[N],pw[N];
struct pi
{
    int x,y;
    bool operator > (const pi &ti) const
    {
        return a[x]+a[y]>a[ti.x]+a[ti.y];
    }
}t;
priority_queue <pi,vector<pi>,greater<pi> > q; 
void solve()
{
    int n,m,i,j,l,r,x,y,tag=0;
    cin>>n; pw[0]=1;
    for(i=1;i<=n;i++)   pw[i]=pw[i-1]*2%M;
    for(i=1;i<=n;i++)   cin>>a[i];
    sort(a+1,a+n+1);
    for(i=n;i>=2;i--)
    {
        while(!q.empty())   q.pop();
        for(j=1;j<i;j++)
            q.push((pi){j,j+1});
        for(j=1;j<i;j++)
        {
            t=q.top();  q.pop();
            b[j]=a[t.x]+a[t.y];
            q.push((pi){t.x,t.y+1});
        }
        tag=(tag+b[1]*pw[i-2])%M;
        for(j=i-1;j>=1;j--)
            b[j]-=b[1];
        for(j=1;j<i;j++)
            a[j]=b[j]%M;
    }
    cout<<(a[1]+tag)%M;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int Ti;
//  for(cin>>Ti;Ti;Ti--)
        solve();    
    return 0;
}