codeforces A. Fox and Box Accumulation 解题报告


题目链接:http://codeforces.com/problemset/problem/388/A

题目意思:有 n 个 boxes,每个box 有相同的 size 和 weight,但是strength 有可能不同。strength的数值表示该box的上面只能放strength 个 boxes,直到放不下,这样就成了一个pile。

问如何叠放使得pile 的个数最少。

     一开始从最底层放置考虑,于是越想越复杂.....

     可以从最高层来开始,那么放在最上面的box的strength最小可以为0,但是stength为0的box在每个pile中最多只可以放一个(0代表这个box上面不能再放任何的box!),接着它的下一层,strength最小都要为1,表示在上面可以放一个(也就是0 strength的box),紧跟着的下一层strength最小为2,.....直到处理最后的一层,于是第一个pile就构成了,而且是最优的。接着下一个pile的构成同上,但要用一个标记vis,防止重复使用第一个pile用过的box。这个过程持续到所有box都构成pile为止。

     

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 100 + 10;
 9 int a[maxn], vis[maxn];
10 
11 int main()
12 {
13     int i, n;
14     while (scanf("%d", &n) != EOF)
15     {
16         for (i = 0; i < n; i++)
17             scanf("%d", &a[i]);
18         memset(vis ,0, sizeof(vis));
19         sort(a, a+n);
20         int ans = 0;
21         int tmp, tol = n;
22         while (tol)
23         {
24             tmp = 0;
25             for (i = 0; i < n; i++)
26             {
27                 if (tmp <= a[i] && !vis[i])
28                 {
29                     vis[i] = 1;
30                     tmp++;    // 下一层需要的最小strength
31                     tol--;   // box用了一个
32                 }
33             }
34             ans++;   // 一个pile建立
35         }
36         printf("%d\n", ans);
37     }
38     return 0;
39 }   

 

智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告