题目链接

题目大意

给一个数组涂色,要求有四点

  1. 要么使用k种颜色中的一个,要不不涂色
  2. 被涂成一种颜色的,值是不同的。
  3. 被涂成每种颜色的值是不一样的。
  4. 满足前三个条件后,要求整个序列涂色的个数尽可能大

解题思路

对于数量多余 k 个的字符,只能取 k 个出来,然后一个一种颜色

小于 k 个的字符就把它们放到一起,然后 1 2 3 … k 1 2 3 … k 这样赋颜色下去就可以了

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5+7;
int T;
int n,m,k;
struct node{
    int num,id;//数值 下标
    int ans;   //答案
}a[N];
int t[N],tt[N];//t[]表示a[i].num的数量(桶)   tt[]表示a[i].num这个桶的编号(用于遍历)
int cmp(node a,node b){
    return a.num<b.num;
}
int cmp_id(node a,node b){
    return a.id<b.id;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>a[i].num;
            t[a[i].num]++;
            a[i].id=i;
        }
        sort(a+1,a+n+1,cmp);//按照数字大小排序便于操作
        int q=1;
        for(int i=1;i<=n;i++){
            if(t[a[i].num]>k){  //如果数量多于k,那么把这个数字从1,2,3...k按顺序给色,多余给0
                tt[a[i].num]++;
                if(tt[a[i].num]>k) a[i].ans=0;
                else a[i].ans=tt[a[i].num];
            }
            else{ //如果数量少于等于k,那么按顺序直接给色
                a[i].ans=q;
                q++;
                if(q>k) q=1;
            }
        }
        for(int i=n;i>=1;i--){ //规则3:每个颜色的色块数量应该是相等的,故将散块中多标出来的删除回去
            if(t[a[i].num]>k) continue;
            if(a[i].ans==k) break;
            a[i].ans=0;
        }
        sort(a+1,a+n+1,cmp_id);//回归答案序
        for(int i=1;i<=n;i++){
            cout<<a[i].ans<<" ";
            t[a[i].num]=0;
            tt[a[i].num]=0;
            a[i].id=a[i].num=a[i].ans=0;
        }
        cout<<endl;
    }
    return 0;
}

分类: 补题

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注