装箱问题(OpenJ_Bailian - 1017)题解

小咪咪 2022-12-28 07:28 102阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入要求
     *  输出要求
     *  样例输入
     *  样例输出
 *  算法分析
 *  解题代码（解法一）
 *  解题代码（解法二）

--------------------

# 题目描述 #

一个工厂制造的产品形状都是长方体，它们的高度都是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

# 算法分析 #

*  从大方块到小方块依次放，不足的空位依次用2\*2，1\*1去补充
 *  对于6\*6方块，1个产品放一层
 *  对于5\*5方块，1个产品放一层，并且有11个1\*1的空位可用
 *  对于4\*4方块，1个产品放一层，并且有5个2\*2的空位可用，或者20个1\*1的空位可用
 *  对于3\*3方块，4个产品放一层，最后不足4个产品时：
 *  (1)剩余1个3\*3方块，放一层，并且有5个2\*2的空位，外加7个1\*1的空位
 *  (2)剩余2个3\*3方块，放一层，并且有3个2\*2的空位，外加6个1\*1的空位
 *  (3)剩余3个3\*3方块，放一层，并且有1个2\*2的空位，外加5个1\*1的空位
 *  对于2\*2方块，9个产品放一层，最后不足9块时用1\*1补充
 *  对于1\*1方块，36个产品放一层，最后直接数量除以36即可

# 解题代码（解法一） #

#include <cstdio>
    #define MAX_(a,b) a>b?a:b
    
    int main(){
        
        int s1, s2, s3, s4, s5, s6;
        while(scanf("%d%d%d%d%d%d", &s1, &s2, &s3, &s4, &s5, &s6) && s1+s2+s3+s4+s5+s6){
        
            int packets = 0;
            packets += s6; // 6*6的产品一个装一箱
            
            packets += s5; // 5*5的产品一个装一箱
            s1 = MAX_(0, s1-11*s5); // 剩余空间用1*1的产品尽量填满
            
            packets += s4; // 4*4的产品一个装一箱
            if(s2<5*s4) s1 = MAX_(0, s1-(5*s4-s2)); // 假如2*2的产品填完之后仍然有空隙，则用1*1填满
            s2 = MAX_(0, s2-5*s4); // 尽量用2*2的产品填满
            
            packets += (s3+3)/4; // 3*3的产品四个一箱
            s3 %= 4;            // 假如3*3的箱子不是四的倍数个，则先用2*2填充再用1*1填充
            if(s3==1){
        
                if(s2<5) s1 = MAX_(0, s1-(27-4*s2));
                else     s1 = MAX_(0, s1-7);
                s2 = MAX_(0, s2-5);
            }
            else if(s3==2){
        
                if(s2<3) s1 = MAX_(0, s1-(18-4*s2));
                else     s1 = MAX_(0, s1-6);
                s2 = MAX_(0, s2-3);
            }
            else if(s3==3){
        
                if(s2<1) s1 = MAX_(0, s1-(9-4*s2));
                else     s1 = MAX_(0, s1-5);
                s2 = MAX_(0, s2-1);
            }
            
            packets += (s2+8)/9; // 2*2的产品九个一箱
            s2 %= 9;             // 假如2*2的箱子不是九的倍数个，则用1*1填充
            if(s2) s1 = MAX_(0, s1-(36-4*s2));
            
            packets += (s1+35)/36; // 1*1的产品三十六个一箱
            
            printf("%d\n", packets);
        }
        
        return 0;
    }

# 解题代码（解法二） #

#include <iostream>
    #include "stdio.h"
    using namespace std;
    const int w = 6;
    const int s = 36;
    int vnum[7];
    int s3[5] = {
        0,5,3,1,0};
    int pick()
    {
        
    	int sum = 0;
    	sum = vnum[6] + vnum[5] + vnum[4] + (vnum[3]+3)/4;
    	int s2 = 5*vnum[4] + s3[vnum[3]%4];
    	if(vnum[2] > s2)
    	{
        
    		sum += (vnum[2] - s2 +8) /9;
    		
    	}
    	int x = 36*(sum-vnum[6]) - 25*vnum[5] - 16*vnum[4] -9*vnum[3] -4*vnum[2];
    	if(vnum[1]>x)
    	sum +=(vnum[1] - x + 35) /36;
    	
    
    	return sum;
    }
    int main(int argc, char *argv[]) {
        
    
    	int end = 0;
    	while(!end)
    	{
        
    		end = 1;
    		for(int i=1;i<7;i++)
    		{
        
    			scanf("%d",&vnum[i]);
    			if(vnum[i]!=0)
    			{
        
    				end = 0;
    			}
    		}
    		
    		if(!end)
    		{
        cout << pick() << endl;}
    	}
    	return 0;
    }