首页 > 代码库 > POJ 1017 Packets
POJ 1017 Packets
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 53686 | Accepted: 18250 |
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
解题思路
这个问题描述得比较清楚,我们在这里只解释一下输入输出样例:共有两组有效输入, 第一组表示有4 个3*3 的产品和一个6*6 的产品,此时4 个 3*3 的产品占用一个箱子,另外 一个 6*6 的产品占用 1 个箱子,所以箱子数是 2;第二组表示有7 个 1*1 的产品,5 个 2*2 的产品和1 个 3*3 的产品,我们可以把他们统统放在一个箱子中,所以输出是1。
分析六个型号的产品占用箱子的具体情况如下:6*6的产品每个会占用一个完整的箱 子,并且没有空余空间;5*5 的产品每个占用一个新的箱子,并且留下 11 个可以盛放 1*1 的产品的空余空间;4*4 的产品每个占用一个新的箱子,并且留下5 个可以盛放2*2 的产品
的空余空间;3*3 的产品情况比较复杂,首先3*3 的产品不能放在原来盛有5*5 或者4*4 的箱子中,那么必须为3*3 的产品另开新的箱子,新开的箱子数目等于3*3 的产品的数目除以 4 向上取整;同时我们需要讨论为3*3 的产品新开箱子时,剩余的空间可以盛放多少2*2 和 1*1 的产品(这里如果有空间可以盛放2*2 的产品,我们就将它计入2*2 的空余空间,等到 2*2 的产品全部装完,如果还有2*2 的空间剩余,再将它们转换成 1*1 的剩余空间)。我们 可以分情况讨论为3*3 的产品打开的新箱子中剩余的空位,共为四种情况:第一种,3*3 的 产品的数目正好是4 的倍数,所以没有空余空间;第二种,3*3 的产品数目是4 的倍数加1, 这时还剩 5 个2*2 的空位和7 个 1*1 的空位;第三种,3*3 的产品数目是4 的倍数加2,这 时还剩3 个2*2 的空位和6 个 1*1 的空位;第四种,3*3 的产品数目是4 的倍数加3,这时 还剩 1 个 2*2 的空位和5 个 1*1 的空位;处理完3*3 的产品,就可以比较一下剩余的2*2 的空位和2*2 产品的数目,如果产品数目多,就将2*2 的空位全部填满,再为2*2 的产品打 开新箱子,同时计算新箱子中 1*1 的空位,如果剩余空位多,就将2*2 的产品全部填入2*2 的空位,再将剩余的 2*2 的空位转换成 1*1 的空位;最后处理 1*1 的产品,比较一下 1*1
的空位与1*1 的产品数目,如果空位多,将1*1 的产品全部填入空位,否则,先将1*1 的空 位填满,然后再为 1*1 的产品打开新的箱子。
下面给出AC代码:
1 #include <stdio.h> 2 int main() 3 { 4 int a,b,c,d,e,f; 5 int y,x;/*y用来存储2*2的空位数目,x用来存储1*1的空位数目*/ 6 int N;/*N用来存储需要的箱子数目*/ 7 int u[4]={0,5,3,1};/*数组u表示3*3的产品数目分别是4的倍数,4的倍数+1,4的倍数加2,4的倍数+3时,为3*3的产品打开的新箱子中剩余的2*2的空位个数*/ 8 while(1) 9 {10 scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);11 if(a==0&&b==0&&c==0&&d==0&&e==0&&f==0)12 break;13 N=f+e+d+(c+3)/4;//这里有一个小技巧:(c+3)/4正好是c/4向上取整的结果14 y=5*d+u[c%4];//计算2*2的空位数目15 if(b>y)//需求>提供16 N+=(b-y+8)/9;//同上,向上取整17 x=N*36-36*f-25*e-16*d-9*c-4*b;18 if(a>x)//需求>提供19 N+=(a-x+35)/36;//同上,向上取整20 printf("%d\n",N);21 }22 return 0;23 }
POJ 1017 Packets