| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 53812 | Accepted: 18299 |
Description
Input
Output
Sample Input
0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0
Sample Output
2 1
Source
题目链接：http://poj.org/problem?id=1017
问题的理解：
①、这道题目的题意理解比较明显，意思就是提供一些底面积为6*6的箱子，各种规格的物品，底面积不一致。要想使得使用的箱子数目最少，那么就是使得每个箱子底面积都装满，显然要从大的物品开始装。问题的关键在于如何计算一个完整的箱子装完一中规格的物品之后，如何去装剩下的其他的物品，空间如何分配。
②、对于6*6的物品的而言，装一个就满了；对于5*5的物品而言，装一个以后还剩下11个1*1的空间，这些空间只能放1*1规格的物品；对于4*4的物品而言，装一个以后还剩下5个2*2的空间，或者是完全换算成20个1*1的空间，当然这里面的空间也可以拆分成部分2*2的空间以及部分1*1的空间；
③、比较难处理的是装3*3规格的物品，一个6*6的箱子最终可以完全装4个3*3的物品，并且需要的箱子数目是3*3的物品的数目除以4向上取整，因为3*3的物品不能和4*4以及5*5的物品放在一起。（向上取整编码时有一个技巧在于不要直接使用向上取整的函数，比如对于除以4向上取整可以编码为 (a+3)/4 。
④、问题的关键在于如何处理最后一个装3*3的箱子其剩下的空间怎么才处理：第一种情况，当装3个3*3物品时，那么还剩下1个2*2和5个1*1的空间；第二种情况，当装2个3*3的物品时，那么还剩下3个2*2和6个1*1的物品空间；第三种情况，当装1个3*3的物品时，那么还剩下5个2*2和7个1*1的物品空间（这个剩余空间的计算方法是按照优先2*2的物品，是的2*2的物品能放的数目最大，然后再考虑1*1的物品）
⑤、剩下的2*2的物品就比较好办了，把前面各物品堆放时的剩下的空间堆放，不够就继续使用新的箱子；
下面给出AC代码：
1 #include <stdlib.h>
2 #include <stdio.h>
3 int main()
4 { 5 int N, a, b, c, d, e, f, y, x; 6 //N表示使用的箱子的数目，a-f一次表示1*1--6*6规格物品的个数 7 //x y是编码时使用的一个技巧，x表示1*1的剩余空间数，y表示2*2 8 //int u[4] = {0,5,3,1}; 9 10 while(1) 11 { 12 scanf("%d %d %d %d %d %d",&a, &b, &c, &d, &e, &f); 13 if(a==0 && b==0 && c==0 && d==0 && e==0 && f==0) 14 break; 15 N = f+e+d+(c+3)/4; //先计算大块头的物品6*6和5*5和4*4以及3*3的物品所需要的箱子 16 17 //关键是计算剩余的 2*2的空间，以最大化2*2的空间为计算标准 18 19 y = d*5; //6*6和5*5的物品均不剩下2*2的空间，一个箱子装一个4*4的物品剩下5个2*2的空间 20 21 if( c%4 == 3) 22 y += 1; 23 else if( c%4 == 2) 24 y += 3; 25 else if( c%4 == 1) 26 y += 5; //这里是关键，把这一个3*3的物品摆放在中间的位置才有可能放入5个2*2的物品 27 28 if( y < b) 29 N += ((b-y)+8)/9; //如果2*2的剩余空间不够，那么就需要新开箱子 30 31 x = 36*N - 36*f - 25*e - 16*d - 9*c - 4*b; //计算剩余的1*1的空间用了一个比较好的方法 32 33 if( x <a) 34 N += ((a-x)+35)/36; //如果1*1的空间不够，那么就需要开新的箱子 35 36 printf("%d\n", N); 37 } 38 return 0; 39 }
