P7390 题解

dAniel_lele · 2025-10-26 23:40:51 · 题解

首先想个假的不能再假的贪心。把每对 (a_i,b_i) 拆成 a_i 个 b_i 扔到一个序列里，然后从大到小两两匹配。

这个的问题是有自环，因此换个角度，从大到小枚举 b_i，用 queue 从大到小维护所有前面的 b_j，每次能合并就合并，不能合并就将剩下来的 b_i（a_i 减去合并次数个）塞到 queue 里面。

这个贪心依然很假，因为你甚至可以连出重边，这同时意味着树会不连通。考虑限制一下能连的边数。不难发现对于一个大小为 S 的点集，设其度数和为 A，那么当度数和 A>2S-2 时，最多连 S-1 条边。否则，最多连 2S-1-A 条边（因为要有边与外界相连）。

容易发现这么做的充要性。利用桶可以做到总复杂度 O(n)。

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
int tp,n;
int a[10000005],b[10000005];
unsigned seed;
unsigned rnd(unsigned x){
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return x;
}
int rad(int x,int y){
    seed=rnd(seed);
    return seed%(y-x+1)+x;
}
void init_data(){
    cin>>seed;
    for(int i=1;i<=n;i++) a[i]=1,b[i]=rad(1,500000);
    for(int i=1;i<=n-2;i++) a[rad(1,n)]++;
}
int cnt[500005],p[10000005];
deque<signed> dq;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>tp>>n;
    if(tp==0){
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
    }
    else init_data();
    for(int i=1;i<=n;i++) cnt[b[i]+1]++;
    for(int i=1;i<=500000;i++) cnt[i]+=cnt[i-1];
    for(int i=1;i<=n;i++) p[++cnt[b[i]]]=a[i];
    int d=2,ans=0;
    for(int i=500000;i>=1;i--){
        for(int j=cnt[i-1]+1;j<=cnt[i];j++){
            int v=p[j];
            d-=2;
            d+=v;
//          cout<<i<<" "<<v<<" "<<d<<"  ";
            while(v--) dq.push_back(i);
            if(d<=0){
                int p=2-d;
                while(dq.size()>p){
                    int fr=dq.front(); dq.pop_front();
                    int bk=dq.back(); dq.pop_back();
                    ans+=fr*bk;
                }
            }
            else{
                while(dq.size()>d){
                    int fr=dq.front(); dq.pop_front();
                    int bk=dq.back(); dq.pop_back();
                    ans+=fr*bk;
                }
            }
//          cout<<ans<<"\n";
        }
    }
    int fr=dq.front(); dq.pop_front();
    int bk=dq.back(); dq.pop_back();
    ans+=fr*bk;
    cout<<ans;
    return 0;
}