Codeforces Round #629 (Div. 3) D. Carousel (贪心）




下面是AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],t,n,fi,be; //a[i]储存答案 fi(first)表示第一个数 ,be(before)表示当前数的前一个数. 
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		cin>>fi;
		int vis=0,k=1;//初始颜色种类k=1. 
		a[1]=1;//a[1]默认为1 
		be=fi; 
		for(int i=2,x;i<=n;i++){
			cin>>x;
			if(x==be) a[i]=a[i-1],vis=i;//vis标记相同的最后一对的位置. 
			else a[i]=3-a[i-1],k=2;
			be=x; //更新 
		}
		if(fi!=be&&a[1]==a[n]){ //特判 
			if(vis){//改变颜色顺序. 
				for(int i=vis;i<=n;i++)
					a[i]=3-a[i];
			}
			else a[n]=3,k=3; 
		}
		cout<<k<<endl;
		for(int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",a[i]); 
	}
	return 0;
}