CF1551B2 题解

原题链接：https://www.luogu.com.cn/problem/CF1551B2

题目分析

本题相比起B1题而言，颜色的数量不固定，并且要求输出的是染色情况。因此可以继续带着B1题的思路做。

1. 用一个数组统计每个数字出现次数，若该数字出现次数小于颜色数量则可以给这个数字染色，反之，第 $k$ 次及以后出现的该数字无法被染色。
2. 用一个 vector 储存能被染色的数字及其输入顺序。
3. 将上述 vector 按照数字从小到大排序，然后依次染上 $k$ 种颜色。
4. 将结果输出。

细节思考

请思考以下两个问题：

1. 为什么要给vector排序？
2. 最多能有多少数字被染色？

以上两条是我认为细节上存在思维难度的地方，核心代码中的注释有详细解释。

核心代码

int main() {
	int m,n,k;
	cin>>m;
	while(m--){
		int cnt[200005],ans[200005],inp;//cnt统计26个字母的个数,ans存储染色结果
		vector<pair <int,int> > v;
		cin>>n>>k;
		for(int i=0;i<=n;i++){
			ans[i]=0;cnt[i]=0;
		}
		for(int i=0;i<n;i++){
			cin>>inp;		
			//cout<<"cnt[inp]: "<<cnt[inp]<<" ";
			if(cnt[inp]<k){
				v.push_back({inp,i});
			}
            		cnt[inp]++;		
		}
		sort(v.begin(),v.end());//排序，目的是为了避免同个数字被染同样色
		int groups=v.size()/k;//把能染色的个数分成k组，设一次染色过程为把k种颜色各自用一遍，groups就是能有几次染色过程
		for(int i=0;i<groups*k;i++){//gruops*k即为保证用各种颜色次数相等时的最大染色数量
			ans[v[i].second]=i%k+1;//染色
		}
		for(int i=0;i<n;i++) cout<<ans[i]<<" ";
		cout<<endl;
	}
	return 0;
}