题目链接: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 }
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。