首页 > 其他分享 >AGC059B

AGC059B

时间:2022-12-11 11:57:32浏览次数:36  
标签:int tp pb -- ans AGC059B first

[[Constructive Algorithms]]

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,a[N],T,tp;
vector<pair<int,int>>x;
#define pb push_back
map<int,int>m;
vector<int>ans;
void dfs(int u){
	ans.pb(x[u].second);x[u].first--;
	while(tp+1<x.size()&&x[u].first>0)
		dfs(++tp),x[u].first--,ans.pb(x[u].second);
	while(x[u].first>0)x[u].first--,ans.pb(x[u].second);
}
int main(){
	cin>>T;
	while(T--){
		cin>>n;m.clear();tp=0;x.clear();ans.clear();
		for(int i=1;i<=n;i++)cin>>a[i],m[a[i]]++;
		for(auto [a,b]:m)x.pb({b,a});
		sort(x.begin(),x.end(),greater<pair<int,int>>());
		if(m.size()*2-2>n) for(auto [a,b]:m)for(int i=1;i<=b;i++) printf("%d ",a);
		else{
			x[0].first++,dfs(0);
			for(int i=0;i+1<ans.size();i++)printf("%d ",ans[i]);
		}
		printf("\n");	
	}
}

标签:int,tp,pb,--,ans,AGC059B,first
From: https://www.cnblogs.com/-WD-/p/16973111.html

相关文章