OpenJudge-1017 装填问题
问题描述
一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。
输入
输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空格隔开，分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。
输出
除了输入的最后一行6个0以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。
样例输入
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
样例输出
2
1
解题思路
总体思路是先将大的产品装完，再将小的产品装在未满的箱子中。
分析六种产品占用箱子的具体情况：
①6*6的产品每个会占用一个完整的箱子，并且没有空余的空间。
②5*5的产品每个会占用一个新的箱子，并且留下了11个可以放1*1产品的空余空间。
③4*4的产品每个会占用一个新的箱子，并且留下了5个可以放2*2产品的空余空间。（如果有空间可以放2*2产品，我们就将它计入为2*2的空余空间，等到2*2产品全被装完后，若还有2*2的空间剩余，再将其转换成1*1的空余空间）
④3*3的产品情况比较复杂，我们需要分情况讨论在为3*3产品新开箱子时，剩余的空间可以放多少个2*2产品和1*1产品，共四种情况。
（1）3*3产品的数目刚好是4的倍数，没有空余的空间。
（2）3*3产品的数目是4的倍数加1，还可以放5个2*2产品和7个1*1产品。
（3）3*3产品的数目是4的倍数加2，还可以放3个2*2产品和6个1*1产品。
（4）3*3产品的数目是4的倍数加3，还可以放1个2*2产品和5个1*1产品。
为3*3产品新开箱子的数目为（x+3）/4，其中x为3*3产品的数目。
⑤接下来处理2*2产品，比较一下空余的2*2的空间数和2*2产品的数目，如果产品数目多，就将2*2的空间全部填满，再为2*2产品开辟新的箱子，同时计算空余的1*1的空间；如果是空余的2*2的空间多，就将2*2产品全部填入2*2的空余空间中，再将剩余的2*2空间转换为1*1的空余空间。
⑥最后处理1*1产品，比较一下1*1的空余空间和1*1的产品数目，如果空余空间多，将1*1的产品全部填入空余空间中，否则，先将空余的1*1空间填满，然后再为1*1产品开辟新的箱子。
AC代码
- 1 import java.util.Scanner;
- 2
- 3 public class Main{
- 4 public static void main(String[] args) {
- 5 Scanner sc=new Scanner(System.in );
- 6
- 7 int[] a=new int[10000];//1*1
- 8 int[] b=new int[10000];//2*2
- 9 int[] c=new int[10000];//3*3
- 10 int[] d=new int[10000];//4*4
- 11 int[] e=new int[10000];//5*5
- 12 int[] f=new int[10000];//6*6
- 13
- 14 a[0]=sc.nextInt();
- 15 b[0]=sc.nextInt();
- 16 c[0]=sc.nextInt();
- 17 d[0]=sc.nextInt();
- 18 e[0]=sc.nextInt();
- 19 f[0]=sc.nextInt();
- 20 int i=0;
- 21 while(!(a[i]==0&&b[i]==0&&c[i]==0&&d[i]==0&&e[i]==0&&f[i]==0))
- 22 {
- 23 i++;
- 24 a[i]=sc.nextInt();
- 25 b[i]=sc.nextInt();
- 26 c[i]=sc.nextInt();
- 27 d[i]=sc.nextInt();
- 28 e[i]=sc.nextInt();
- 29 f[i]=sc.nextInt();
- 30 }
- 31 for(int k=0;k<i;k++)
- 32 {
- 33 System.out.println(min(a[k],b[k],c[k],d[k],e[k],f[k]));
- 34 }
- 35
- 36
- 37 }
- 38 //对应于 1 2 3 4 5 6
- 39 public static int min(int q,int w,int e,int r,int t, int y)//所需的最小包裹数
- 40 {
- 41 int[] k= {0,5,3,1};//装3*3产品时，还能放下多少个2*2产品
- 42 int sum=0;//sum为所需的包裹数
- 43 int m=0;//剩下还能装多少个2*2产品
- 44 int n=0;//剩下还能装多少个1*1产品
- 45 sum=y+t+r+(e+3)/4;
- 46 m=5*r+k[e%4];
- 47 if(w>m)
- 48 {
- 49 sum=sum+(w-m+8)/9;//需要再增加包裹的数目
- 50 }
- 51 n=36*sum-36*y-25*t-16*r-9*e-4*w;//面积即个数
- 52 if(q>n)
- 53 {
- 54 sum=sum+(q-n+35)/36;
- 55 }
- 56 return sum;
- 57 }
- 58 }