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

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

阅读量：7294 次

发布时间：2019-06-30

本文共 2595 字，大约阅读时间需要 8 分钟。

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 
     
       11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 #include 
          
            16 #include 
            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]) ? '\n' : ' '); 49 if (t == k) t = 0; 50 } 51 } 52 } 53 else 54 puts ("NO"); 55 } 56 57 return 0; 58 } 59

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 #include 
             
               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 
              
                v[MAXN];16 17 int main(void)18 {19 #ifndef ONLINE_JUDGE20 freopen ("B.in", "r", stdin);21 #endif22 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
               
                :: 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]) ? '\n' : ' ');67 if (t == k) t = 0;68 }69 }70 }71 else72 puts ("NO");73 }74 75 return 0;76 }