题目链接：http://codeforces.com/problemset/problem/509/B

 

题意：有n堆石头，每堆有ai个,有k种颜色要求给所有石头涂上色。要求任意两堆石头中相同颜色的石头的数量之差小于等于1。 1<=n,k,ai<=100

 

思路：

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

  1. 考虑到求出最小的一堆石子数量，设为mina

  2. 然后将每堆的前mina+1个石子（能染多少是多少）染成1（方便起见）颜色。

  3. 后面的石子按顺序染颜色2~k即可。

例如[样例3]：

  1. 先求出mina=min{3,2,4,3,5}=2

  2. 然后按照[步骤2]将每堆的前三颗石子染成11颜色，结果如下：

    1 1 1 1 1 1 1 1 ? 1 1 1 1 1 1 ? ?

    其中?表示还未染色的石子

  3. 然后按照[步骤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。

 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 const int maxn=2e5+7;
 8 
 9 int n,k;
10 int arr[maxn];
11 int vis[maxn];
12 int Print[maxn][maxn];
13 
14 void draw(int num,int id){
15     for (int i=0;i<n;i++){
16         int cnt = num;
17        for (;vis[i]<arr[i] && cnt;vis[i]++,cnt--){
18             Print[i][vis[i]] = id;
19         }
20     }
21 }
22 
23 int main(){
24     scanf("%d%d",&n,&k);
25     int minxx = 0x3f3f3f3f;
26     for (int i=0;i<n;i++) {
27         scanf("%d", &arr[i]);
28         if (arr[i] < minxx) {
29             minxx = arr[i];
30         }
31     }
32         draw(minxx+1,1);
33         for (int i=2;i<=k;i++){
34             draw(1,i);
35         }
36         for (int i=0;i<n;i++){
37             if (vis[i] != arr[i]){
38                 printf("NO\n");
39                 return 0;
40             }
41         }
42         printf("YES\n");
43         for (int i=0;i<n;i++){
44             for (int j=0;Print[i][j]!=0;j++){
45                 printf("%d ",Print[i][j]);
46             }
47             printf("\n");
48         }
49         return 0;
50 }