贪心 Codeforces Round #289 (Div. 2, ACM ICPC Rules) B. Painting Pebbles

  1 /*
  2     题意：有 n 个piles，第 i 个 piles有 ai 个pebbles，用 k 种颜色去填充所有存在的pebbles，
  3             使得任意两个piles，用颜色c填充的pebbles数量之差 <= 1。
  4             如果不填充某种颜色，就默认数量为0。
  5     1. 贪心：如果个数之间超过k个，那么填充什么颜色都会大于1，巧妙地思维
  6         详细解释：http://blog.csdn.net/haoliang94/article/details/43672617
  7     2. 比较每种填充颜色在n组里使用最多和最少的，若差值<=1，则YES，否则NO
  8         详细解释：http://www.cnblogs.com/windysai/p/4265469.html
  9 */
 10 #include <cstdio>
 11 #include <iostream>
 12 #include <cmath>
 13 #include <algorithm>
 14 #include <cstring>
 15 #include <string>
 16 #include <map>
 17 using namespace std;
 18 
 19 const int MAXN = 200 + 10;
 20 const int INF = 0x3f3f3f3f;
 21 int a[MAXN];
 22 
 23 int main(void)
 24 {
 25     #ifndef ONLINE_JUDGE
 26     freopen ("B.in", "r", stdin);
 27     #endif
 28 
 29     int n, k;
 30     while (~scanf ("%d%d", &n, &k))
 31     {
 32         int mx = -1;    int mn = INF;
 33         for (int i=1; i<=n; ++i)
 34         {
 35             scanf ("%d", &a[i]);
 36             if (mx < a[i])    mx = a[i];
 37             if (mn > a[i])    mn = a[i];
 38         }
 39 
 40         if (mx - mn <= k)
 41         {
 42             puts ("YES");
 43             for (int i=1; i<=n; ++i)
 44             {
 45                 int t = 0;
 46                 for (int j=1; j<=a[i]; ++j)
 47                 {
 48                     printf ("%d%c", ++t, (j==a[i]) ? '
' : ' ');
 49                     if (t == k)    t = 0;
 50                 }
 51             }
 52         }
 53         else
 54             puts ("NO");
 55     }
 56 
 57     return 0;
 58 }
 59

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <string>
 7 #include <map>
 8 #include <vector>
 9 using namespace std;
10 
11 const int MAXN = 100 + 10;
12 const int INF = 0x3f3f3f3f;
13 int a[MAXN];
14 int cnt[MAXN];
15 vector <int> v[MAXN];
16 
17 int main(void)
18 {
19     #ifndef ONLINE_JUDGE
20         freopen ("B.in", "r", stdin);
21     #endif
22 
23     int n, k;
24     while (~scanf ("%d%d", &n, &k))
25     {
26         for (int i=1; i<=MAXN; ++i)
27             v[i].clear ();
28         
29         for (int i=1; i<=n; ++i)
30         {
31             scanf ("%d", &a[i]);
32             memset (cnt, 0, sizeof (cnt));
33             int t = 0;
34             for (int j=1; j<=a[i]; ++j)
35             {
36                 cnt[++t]++;
37                 if (t == k)    t = 0;
38             }
39             for (int j=1; j<=k; ++j)
40             {
41                 v[j].push_back (cnt[j]);
42             }
43         }
44 
45         bool flag = true;
46         vector<int>:: iterator it1, it2;
47         for (int i=1; i<=k; ++i)
48         {
49             sort (v[i].begin (), v[i].end ());
50             it1 = v[i].end () - 1;
51             it2 = v[i].begin ();
52             if (*it1 - *it2 > 1)
53             {
54                 flag = false;    break;
55             }
56         }
57 
58         if (flag)
59         {
60             puts ("YES");
61             for (int i=1; i<=n; ++i)
62             {
63                 int t = 0;
64                 for (int j=1; j<=a[i]; ++j)
65                 {
66                     printf ("%d%c", ++t, (j==a[i]) ? '
' : ' ');
67                     if (t == k)    t = 0;
68                 }
69             }
70         }
71         else
72             puts ("NO");
73     }
74 
75     return 0;
76 }

解法2

编译人生，运行世界！