【Codeforces Round #531 (Div. 3) B. Array K-Coloring】暴力

B. Array K-Coloring

题意

给定n和k,$1<=n,k<=5000$，和n个数
要求用k种颜色对n个数进行涂色，要求每种颜色至少出现过一次，
而且同一种颜色不能对相同的数字涂色，求是否有合法的涂色方案。

做法

首先如果一个数字出现次数超过k，肯定没有合法的涂色方案
如果n<k，也没有合法方案。
之后就先用1-k涂前1-k个数字，之后暴力判断每个数字可以用哪个颜色，
可以的话就涂色并用二维数组记录,vis[i][j]表示第i种颜色涂过j数字。

代码

#include<stdio.h>
const int maxn = 1e5+5;
int a[maxn];
int sum[maxn];
int ans[maxn];
bool vis[5005][5005];
int main()
{
    int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) sum[a[i]]++;for(int i=1;i<=5000;i++){
    if(sum[i]>k){
    printf("NO\n");return 0;}}if(n<k){
    printf("NO\n");return 0;}int pos=1;for(int i=1;i<=n;i++){
    if(pos<=k){
    ans[i]=pos;vis[pos][a[i]]=1;pos++;}else{
    for(int j=1;j<=k;j++){
    if(vis[j][a[i]]==0){
    ans[i]=j;vis[j][a[i]]=1;break;}}}}printf("YES\n");for(int i=1;i<=n;i++) printf("%d ",ans[i]);return 0;
}