专栏文章

P7390 题解

ddAniel_lele正虚像
P7390题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhlvmp
此快照首次捕获于
2025/12/02 02:33
3 个月前
此快照最后确认于
2025/12/02 02:33
3 个月前
查看原文
首先想个假的不能再假的贪心。把每对 (ai,bi)(a_i,b_i) 拆成 aia_i 个 bib_i 扔到一个序列里，然后从大到小两两匹配。
这个的问题是有自环，因此换个角度，从大到小枚举 bib_i，用 queue 从大到小维护所有前面的 bjb_j，每次能合并就合并，不能合并就将剩下来的 bib_i（aia_i 减去合并次数个）塞到 queue 里面。
这个贪心依然很假，因为你甚至可以连出重边，这同时意味着树会不连通。考虑限制一下能连的边数。不难发现对于一个大小为 SS 的点集，设其度数和为 AA，那么当度数和 A>2S−2A>2S-2 时，最多连 S−1S-1 条边。否则，最多连 2S−1−A2S-1-A 条边（因为要有边与外界相连）。
容易发现这么做的充要性。利用桶可以做到总复杂度 O(n)O(n)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...