题目大意
给一个数组涂色,要求有四点
- 要么使用k种颜色中的一个,要不不涂色
- 被涂成一种颜色的,值是不同的。
- 被涂成每种颜色的值是不一样的。
- 满足前三个条件后,要求整个序列涂色的个数尽可能大
解题思路
对于数量多余 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 条评论