文章目录
Part1：题目链接
点我就送新阿姆斯特朗回旋加速喷气式阿姆斯特朗大炮[doge]
Part2：题意
现给出一个长度为N的数字序列，对于给出序列我们会对其中的每个数字使用k种颜料进行涂色。
涂色之后的序列需要满足：
1.对于任意一个数字，它只能被涂上一种颜色，或是不涂色。
2.被涂上同一种颜色的数字不能出现重复现象。
3.每种颜色所上色的数字数量需相同。
4.在满足前三者的条件下，我们希望被上色的数字越多越好。
例题：序列 [3 ，1 ，1 ，1 ，1 ，10 ，3 ，10 ，10 ，2]的上色结果：
Part3：思路
懒狗博主更新了。
昨晚的div3，由于刚跑完步累成doge，再加上期末和暑期设计，很久没碰代码了，打的不是很好。
这题我的思路是正确的，但是有一个参数我算错了，导致W掉了。今天再想的时候就秒A了，昨天有点累坏了。
这题其实不难，题意很明显，是一个贪心题。
首先我们可以从题目中得到以下几点
1.在最后得到的序列中，非0数字的个数一定为k的倍数。
2.对于一个数字，如果出现了k次以上（包含k次），那么至多只有前k次出现时会被涂色；否则都有可能被涂色。
接下来我们需要先想出非0数字的个数究竟是k的多少倍。
其实很简单，按照我们所说的第二条，
如果没有规则三的限制，那么对于所有出现的数字，出现次数大于k的可以保证前k个有颜色，出现次数小于k的则一定都能被涂色，这时可以被涂色的数字个数设为num。
这里我们说的是没有规则三（每种颜色所上色的数字数量需相同。）的约束下会产生的结果。
但加了规则三之后，我们需要涂色的个数就只能是k的x倍，那么x=num/k。
（我的唯一一发WA就是因为这个，呜呜呜，顶不住了）
接下来贪心就可以了，就顺着向下涂色，顺序无所谓的。
「伊丽莎白」，放代码！
Part4：AC代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f
#define pi acos(-1)
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
int b[maxn];
int main()
{
int t;
cin>>t;
while(t--){
int n,k,x;
cin>>n>>k;
map<int,vector<int> >p; //数字->数字出现的位置s
for(int i=0;i<n;i++){
cin>>x;
p[x].push_back(i);
}
memset(b,0,sizeof(b));
map<int,vector<int> >::iterator it;
int nowk=1,ans=0; //ans：记录倍数
int num=0;
for(it=p.begin();it!=p.end();it++){ //筛选出有用的num，上文中有说明
num+=((it->second).size()>k?k:(it->second).size());
}
//cout<<num<<endl;
for(it=p.begin();it!=p.end();it++){
int limitk=nowk-1; //思路中总结出的第2条，为了限制一个数字被涂色的次数
for(int i=0;i < it->second.size();i++){
b[(it->second)[i]]=nowk;
nowk++;
if(nowk>k) nowk=1,ans++;
if(nowk==limitk+1) break;
if(ans==num/k) break;
}
if(ans==num/k) break;
}
for(int i=0;i<n;i++){
if(i) cout<<" ";
cout<<b[i];
}
cout<<endl;
}
return 0;
}
Part5：整活时间
选自《银魂》第56话
真选组·近藤勋：
“阿通，很抱歉啊。还亏你帮我们那么多忙，但归根到底我们就是这么一群人。
虽然想要改变，但还是一点都没变，我们还是一群又愚蠢又粗野的，被人讨厌的无能的废物。
看来这种无能不是一朝一夕就改得了的。
但是说，就像阿通说的一样，如果重新审视自己就会有新的发现。
不管我们多么被人讨厌，多么受人嘲笑都没关系。
但是决不想成为保护不了自己应该保护的东西的男人。”