锐客网

  1. 首页 > it技术 > >

CodeForces1102B--Array K-Coloring--思维

模拟

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

  • Each element of the array should be colored in some color;
  • For each ii from 11 to kk there should be at least one element colored in the ii-th color in the array;
  • For each ii from 11 to kk all elements colored in the ii-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,…cnc1,c2,…cn, where 1≤ci≤k1≤ci≤k and cici is the color of the ii-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 nn and kk (1≤k≤n≤50001≤k≤n≤5000) — the length of the array aa and the number of colors, respectively.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤50001≤ai≤5000) — elements of the array aa.
Output
If there is no answer, print "NO". Otherwise print "YES" and anycoloring (i.e. numbers c1,c2,…cnc1,c2,…cn, where 1≤ci≤k1≤ci≤k and cici is the color of the ii-th element of the given array) satisfying the conditions described in the problem statement. If there are multiple answers, you can print any.
Examples
Input
4 2 1 2 2 3

Output
YES 1 1 2 2

Input
5 2 3 2 1 2 3

Output
YES 2 1 1 2 1

Input
5 2 2 1 1 2 1

Output
NO

Note
In the first example the answer 2 1 2 12 1 2 1 is also acceptable.
In the second example the answer 1 1 1 2 21 1 1 2 2 is also acceptable.
There exist other acceptable answers for both examples.
给k颜色，n个数，问能不能用完所有的颜色且数学相同的颜色不同。
先用完这些颜色，再判断这些数哪种颜色没有用过。注意NO的情况。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define maxn 5006 int a[maxn]; int vis[maxn]; int vis1[maxn]; int ans[maxn][maxn]; int w[maxn]; int main() { int n,k; scanf("%d%d",&n,&k); int flag=0; for(int i=1; i<=n; i++) { int x; scanf("%d",&x); a[i]=x; vis[x]++; if(vis[x]>k) { flag=1; } } if(flag||k>n) { printf("NO\n"); } else { memset(vis,0,sizeof(vis)); int num=0; for(int i=1; i<=k; i++) { //cout<

【CodeForces1102B--Array K-Coloring--思维】

    推荐阅读


    上一篇：linux进程通信（一）--共享内存+信号量，代码示例

    下一篇：js增加给指定id下图片下增加链接