题目要求:
有n堆石头,每堆有ai个,有k种颜色要求给所有石头涂上色。要求任意两堆石头中相同颜色的石头的数量之差小于等于1。 1<=n,k,ai<=100
1.存在性判断,不存在输出 NO
2.存在,然后构造每个石堆颜色
既然限制是差值,那么可以先考虑,最小的和最大的差值
比如随便构造一个 用例
4 3
5 6 7 11
最小为 5,最大为 11
先考虑颜色相同,即最倒霉情况(最不利), 那么
1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
那么相同颜色差值为 11 - 5 = 6 ,显然不符合题意了
如果要减少这个差值,那么需要改变 石堆2 的某些石子颜色
1 1 1 1 1
1 1 1 1 1 1 2 3 1 1 1 —>方案1
1 1 1 1 1 1 2 2 3 3 1 —>方案2
而颜色数为3,所以根据鸽巢原理和最不利构造法,颜色差最小都为2,不满足
所以存在性判断就出来了,对比最小石堆和最大石堆即可
看其差值是否 大于颜色数 k 即可,
否则根据鸽巢原理,比存在颜色石头数差值大于 1 即可
if(maxs-mins>k){
cout<<"NO"<<endl;
return 0;
}
如果,最大和最小的满足条件了,即最极端的情况满足了,那么其他的肯定也满足
构造阶段:贪心
以最小值为基准,染上颜色1
其他,在其基础上加1,染上颜色1
然后剩下的,逐个染色,每次颜色+1即可
代码如下:
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 105;
int arr[MAXN];
int n,k;
int main(){
cin>>n>>k;
int mins = MAXN;
int maxs = 0;
for(int i=1;i<=n;i++){
cin>>arr[i];
mins = min(mins,arr[i]);
maxs = max(maxs,arr[i]);
}
if(maxs-mins>k){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
for(int i=1;i<=n;i++){
int end = min(arr[i],mins+1);
for(int j=1;j<=end;j++){
cout<<1<<' ';
}
int c = 2;
for(int j=end+1;j<=arr[i];j++){
cout<<c++<<' ';
}
cout<<endl;
}
return 0;
}