题目:https://codeforces.com/contest/1551/problem/B2
题解:用map<int, vector<int> >mp;记录下标 。然后进行遍历,每个数一次性处理。
//#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;
int ans[200005];
int main()
{
int t;
cin >> t;
while (t--)
{
map<int, vector<int> >mp;
int n, k;
int s = 0;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
int t;
cin >> t;
mp[t].push_back(i);//下标标记
if (mp[t].size() <= k)
{
s++;
}
}
s /= k;//每种颜色涂几次
int color = 1;
int all = s * k;//可以涂的数
int t = 0;//涂了几个
for (auto it = mp.begin(); it != mp.end(); it++)
{
int size = it->second.size();
int tu = min(size, k);
for (int i = 0; i < tu; i++)
{
int tpos = it->second[i];//这个数的下标
if (t >= all)
{
ans[tpos] = 0;
break;
}
ans[tpos] = color;
color %= k;
color++;
t++;
}
for (int i = tu; i < size; i++)
{
ans[it->second[i]] = 0;
}
}
for (int i = 0; i < n; i++)
{
cout << ans[i] << " ";
}
cout << endl;
}
}