ZOJ 4102 2019浙江省試合C題Array in the Pocket

17098 ワード

まずset貪欲に最小を取るが、B集合に記入されていない個数が最も多い要素にA集合に記入される要素を加え、残りの要素数より多くしてはならない.そうしないと、その要素を取る.1 1 2 2 3 3 2 2 2 2 2番目の要素が2を埋めると残りの3の個数に、Aの残りの3の個数が(6/2)(6は残りの要素の個数)より多いので、2番目の要素は3しか記入できませんもちろん、最初からn/2より多くの要素があれば、Impossibleを出力します.
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int a[M],b[M];
int c[M],cc[M];
typedef pair<int,int> P;
set<P> s1,s2;
set<P>::iterator it,mx;
int main(){
	int t,n;
	cin>>t;
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			a[i]=b[i]=c[i]=cc[i]=0;
		}
		s1.clear();s2.clear();
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			c[a[i]]++;cc[a[i]]+=2;
			
		}
		for(int i=1;i<=n;i++){
			if(c[i]){
				s1.insert(P(i,c[i]));
			    s2.insert(P(cc[i],i));
			}
			
		}
		//int temp=(*(--s2.end()))->first;
		it=s2.end();
		it--;
		int temp=it->first;
		if(temp>n){
			printf("Impossible
"
); continue; } for( int i=1;i<=n;i++){ s2.erase(P(cc[a[i]],a[i])); s2.insert(P(--cc[a[i]],a[i])); it=s1.begin(); mx=s2.end(); mx--; if(mx->first==n-i+1){ b[i]=mx->second; } else { if(a[i]==it->first)it++; b[i]=it->first; } s1.erase(P(b[i],c[b[i]])); c[b[i]]--; s2.erase(P(cc[b[i]],b[i])); cc[b[i]]--; if(c[b[i]])s1.insert(P(b[i],c[b[i]])); if(cc[b[i]])s2.insert(P(cc[b[i]],b[i])); } cout<<b[1]; for(int i=2;i<=n;i++){ printf(" %d",b[i]); } printf("
"
); } }