题解
这题本质上其实就是[贪心]
考虑到求出最小的一堆石子数量,设为mina
,即其中mina=\min\limits_{1\leq{i}\leq{n}}\{a[i]\}。
然后将每堆的前mina+1
个石子(能染多少是多少)染成1(方便起见)颜色。
后面的石子按顺序染颜色2~k即可。
例如[样例3]:
先求出mina=\min\{3,2,4,3,5\}=2
然后按照[步骤2]将每堆的前三颗石子染成1颜色,结果如下:
1 1 1
1 1
1 1 1 ?
1 1 1
1 1 1 ? ?
其中?
表示还未染色的石子
然后按照[步骤3]染即可,就成功了(注意此题SPJ
)
1 1 1
1 1
1 1 1 2
1 1 1
1 1 1 2 3
不可能的情况也很简单,仔细想想就知道当且仅当任意一堆染得石子数量不足本队石子总数(即mina+k+1<a[i]
),才输出NO
。
代码
#include<stdio.h>
int n,k,a[110],mina=233333333,times,used[110],res[110][110]; //其中used[i]表示第i堆石子已经染了used[i]颗石子
void paint(int num,int id)
{
for(register int i=1;i<=n;++i)
{
times=num; //倒计时染色石子颗数
for(;used[i]<a[i]&×++used[i],--times) res[i][used[i]+1]=id; //注意染的数量的限制(used[i]<a[i])
}
return ;
}
int main()
{
scanf("%d%d",&n,&k);
for(register int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
if(a[i]<mina) mina=a[i]; //求mina
}
paint(mina+1,1); //步骤2
for(register int i=2;i<=k;++i) paint(1,i); //步骤3
for(register int i=1;i<=n;++i) //若任意一堆染得石子数量不足本队石子总数,就输出NO
{
if(used[i]!=a[i]) //同理
{
printf("NO\n");
return 0;
}
}
printf("YES\n"); //记得输出YES
for(register int i=1;i<=n;++i)
{
for(register int j=1;j<=a[i];++j) printf("%d ",res[i][j]); //输出染色结果
putchar('\n');
}
return 0;
}