Codeforces Round #734 (Div. 3)B2. Wonderful Coloring

Div. 3)B2. Wonderful Coloring"/>

Codeforces Round #734 (Div. 3)B2. Wonderful Coloring

B2. Wonderful Coloring - 2（构造）

题目大意：
给一串数，用 k k k种颜色来进行染色每种颜色所使用的次数相同，且不能有重复元素。

思路：
字符串模拟题，亦直 w a wa wa，凡死了。。。

对于给定的数组，我们用一个 p a i r pair pair数组存储其数值以及坐标。按从小到大进行排序，这样方便我们染色，

（插播一个小知识， p a i r pair pair数组默认按 f i r s t first first排序）。

排序之后我们用一个 q q q来记录其个数，如果大于 k k k我们就将其大于k的部分都染为 0 0 0，否则就按顺序染色。

将所有的数都染色完毕后，我们还需要检查，如果最后一个不为 0 0 0的数所染的色不是 k k k，那么我们就要让他一直到上一个 k k k都染为 0 0 0才可以。

染色完之后对于所有数的坐标和染色一一对应放入另一个 p a i r pair pair数组中排序输出即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<sstream>
#include<queue>
#define fr for
#define pi 3.1415926535
#define me(a,b,c) memset(a,b,sizeof c)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
const int N = 1e6 + 10;int a[N];
pii b[N], ans[N];
int c[N];
int main() {int t;cin >> t;while (t--){int n, k;cin >> n >> k;fr(int i = 1; i <= n; i++)b[i].first = b[i].second = c[i] = 0;for (int i = 1; i <= n; i++)cin >> a[i];fr(int i = 1; i <= n; i++)b[i] = { a[i],i };sort(b + 1, b + 1 + n);int q = 1;int num = 1;c[1] = 1;fr(int i = 2; i <= n; i++) {if (b[i].first == b[i - 1].first) {q++;if (q > k) {c[i] = 0;continue;}}else q = 1;num++;if (num > k)num = 1;c[i] = num;}int i = n;while (c[i] != k){c[i] = 0;i--;}for (int i = 1; i <= n; i++)ans[i] = { b[i].second,c[i] };sort(ans + 1, ans + 1 + n);cout << ans[1].second;fr(int i = 2; i <= n; i++)cout << ' ' << ans[i].second;puts("");}
}