思路：
分类讨论：
当一个数字出现的次数大于等于k，那么最多有k个能被染色，
当一个数字出现的次数小于k，南那么这些数字都可能被染色
还有一个条件就是需要满足每个颜色的数字个数一样多，这里记出现次数小于k的所有数字的出现次数总和为sum，将所有这些数字排序后，前sum-sum%k个数字是都可以被染色的，按照1~k的顺寻依次染色即可。
主要是有点不太好实现。
对于这种我们需要统计每个数字有多少个，同时还需要保留每个数字的下标信息的我们可以开多个vector去维护
对于不需要的直接开一个桶就行。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
using namespace std;
const int N=2e5+10,mod=1e9+7;
int a[N];
int ans[N];
vector<int>tong[N];
bool vis[N];
void solve()
{
int n,k;cin>>n>>k;
rep(i,1,n)
{
vis[i]=a[i]=ans[i]=0;
if(tong[i].size()) tong[i].clear();
}
rep(i,1,n)
{
int x;cin>>x;
a[i]=x;
tong[x].push_back(i);
}
vector<int>b;
rep(i,1,n)
{
if(!vis[a[i]]&&tong[a[i]].size()>=k)
{
rep(j,1,k) ans[tong[a[i]][j-1]]=j;
vis[a[i]]=1;
}
else if(!vis[a[i]]&&tong[a[i]].size()>0)
{
rep(j,0,tong[a[i]].size()-1) b.push_back(tong[a[i]][j]);
vis[a[i]]=1;
}
}
int ss=b.size();
rep(i,0,ss-ss%k-1) ans[b[i]]=(i%k+1);
rep(i,1,n) cout<<ans[i]<<' ';
cout<<endl;
}
signed main()
{
IOS
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
参考洛谷上大佬的代码写的显然简洁很多。
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;
}