CF1551B2 Wonderful Coloring - 2（贪心，思维)

原题链接

题目

思路

通过举例子：

可知：

1. 每种数字最多只能被染成 k 种不同的颜色。

所以对于每个数字：

1. 存储下每个位置
2. 算出最多有多少数可供染色（每种数全用，超过 k 的算成 k个数），然后求出每种颜色可以染多少个数。
3. 然后就遍历每个数的每个位置，依次染色。
4. 一旦哪个颜色的数量超过之前算出的应有数量，就还原该位置上的颜色，然后退出染色，输出答案。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
vector<int> g[N];int main()
{
    int t; cin >> t;while (t -- ){
    int n, k; cin >> n >> k;for (int i = 0; i <= n; i ++ ) g[i].clear();int a[n + 10];unordered_map<int, int> ma;unordered_set<int> s;for (int i = 1; i <= n; i ++ ){
    cin >> a[i];s.insert(a[i]);ma[a[i]] = min(ma[a[i]] + 1, k);g[a[i]].push_back(i);}int sum = 0;for (auto i : s) sum += ma[i];int cnt = sum / k;int res[N] = {
    0};int ans[N] = {
    0};int c = 1;bool f = 0;for (auto i : s){
    int x = i;int v = g[x].size();for (int j = 0; j < min(k, v); j ++ ){
    int tt = g[x][j];ans[tt] = c;res[c] ++;if (res[c] > cnt){
    f = 1;ans[tt] = 0;break;}c ++;if (c > k) c = 1;}if (f) break;}for (int i = 1; i <= n; i ++ ) cout << ans[i] << " " ;cout << endl;}return 0;
}

总结

本题考察了 stl 的用法。

遇到问题时要手算去推一推。