『算法-ACM 竞赛-CodeForces』 1102B Array K-Coloring

B. Array K-Coloring time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output

describe

You are given an array a consisting of n integer numbers.
You have to color this array in k colors in such a way that:

Each element of the array should be colored in some color;
For each i from 1 to k there should be at least one element colored in the i-th color in the array;
For each i from 1 to k all elements colored in the i-th color should be distinct.
Obviously, such coloring might be impossible. In this case, print “NO”. Otherwise print “YES” and any coloring (i.e. numbers c1,c2,…cn, where 1≤ci≤k and ci is the color of the i-th element of the given array) satisfying the conditions above. If there are multiple answers, you can print any.

Input

The first line of the input contains two integers n and k (1≤k≤n≤5000) — the length of the array a and the number of colors, respectively.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤5000) — elements of the array a.

Output

If there is no answer, print “NO”. Otherwise print “YES” and any coloring (i.e. numbers c1,c2,…cn, where 1≤ci≤k and ci is the color of the i-th element of the given array) satisfying the conditions described in the problem statement. If there are multiple answers, you can print any.

Examples

4 2
1 2 2 3
YES
1 1 2 2
5 2
3 2 1 2 3
YES
2 1 1 2 1
5 2
2 1 1 2 1
NO
Note

In the first example the answer 2 1 2 1 is also acceptable.

In the second example the answer 1 1 1 2 2 is also acceptable.

There exist other acceptable answers for both examples.

这是一道简单的思维题，题意是说有 w 个数字，n 种颜色，刷漆，每种颜色的油漆刷的元素必须不同。我写的应该算得上简单了，也容易理解，因为给的数值范围很小，所以也不用离散化直接用数组代表出现的次数，先用了一个 ob[]数组，记录这个数字出现的次数，再用一个 ans 数组记录它的颜色，这时候你会发现这题好简单，出现 1 次颜色是 1，出现两次颜色是 2，出现次数超过给定颜色，不成立输出 NO,好了你成功入坑了，这个题要求每个颜色至少使用一次，做了一个小操作，详情看代码!这是你觉得万事大吉了，WA 四次终于明白，原来当颜色比数字多的时候，永远可能使每个颜色至少使用一次，现在题意跟坑清晰了，可以敲代码了。
AC code

#include<iostream>
#include<cstring>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
int ob[5050]，ans[5050]，ao[5050];
int main()
{
    int n,w,x,flag=1,flag2=0;
    mst(ans,0);
    mst(ob,0);
    cin>>n>>w;
    if(n<w) flag=0;
    for(int i=1;i<=n;i++){
        cin>>x;
        ob[x]++;
        ans[i]=ob[x];
        ao[ans[i]]++;
        flag2=max(flag2,ans[i]);
        if(ob[x]>w) flag=0;
    }
    int t=1;
        if(flag){
        while(flag2!=w){
                if(ao[ans[t]]>=2){
                    ao[ans[t]]--;
                    ans[t++]=++flag2;
                }
                else t++;
            }
            cout<<"YES"<<endl;
            for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
            return 0;
        }
        else cout<<"NO";
        return 0;
}