洛谷CF509B题解

damage

题解

这题本质上其实就是[贪心]

考虑到求出最小的一堆石子数量，设为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]&&times;++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;
}