Wonderful Coloring

Wonderful Coloring"/>

Wonderful Coloring

Wonderful Coloring - 2 贪心

题目来源：Codeforces Round #734 (Div. 3) B2

description

有一个元素是整数的数列，有k个颜色去涂这些元素
求涂色方案，需满足以下条件
（1）每一个元素都可以涂成一种颜色或者不涂；
（2）要求数值一样的元素不能涂相同颜色；
（3）并且k个颜色分别涂的数量要相等
（3）在此基础上我们的方案是让涂色的元素数量最大，可能会有多种方案，输出一种

solution

直接贪心：
  简单的做法就是排个序，然后如果一个整数的数量大于k，就k个颜色都涂一遍，剩下的不涂，其他的就按顺序1，2，3,…,k 这样涂下去然后循环。
  最后一个循环涂色时很大可能会出现1->k没有遍历完的情况也就是涂色数量不等了，这不符合要求，所以把这些"尾巴"选择不涂色。
  方便编程我写了多个数组去存取不同阶段的数列，具体实现看代码。
（有更巧妙的方法不需要排序）

Code

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 2e5;
int a[MAXN+10];
int b[MAXN+10];
int c[MAXN+10]; 
queue<int> q[MAXN+10];
int main()
{ios::sync_with_stdio(false);int t;cin>>t;while(t--){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];c[i] = a[i];  // 保存原始数组至 c }sort(a+1,a+n+1); // dont forget +1 int j=1;int cnt=1;b[1]=a[1];// 将已经排好序的 a数组去掉数量大于 k的元素然后放到 b数组中 for(int i=2;i<=n;i++){//当前连续cnt个 if(a[i]==a[i-1]){cnt++;}else{cnt=1;}//连续cnt个是否超过k if(cnt<=k){j++;b[j]=a[i];}else{continue;}}int n2 = j/k*k;  // 多余的余数部分就不要了 int now=1;for(int i=1;i<=n2;i++){//cout<<b[i]<<" ";//cout<<"in "<<now<<endl;q[b[i]].push(now);  // 利用queue保存每一个整数的涂色方案 now++;if(now>k) now=1;}// output for(int i=1;i<=n;i++){if(q[c[i]].empty()) {cout<<"0 ";}else{int ft = q[c[i]].front();q[c[i]].pop();cout<<ft<<" ";}}cout<<endl;}return 0;
}