[[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