1226：裝箱問題

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 5923 ??? 通過數: 3064

【題目描述】

一個工廠制造的產品形狀都是長方體，它們的高度都是h，長和寬都相等，一共有六個型號，他們的長寬分別為1×1,2×2,3×3,4×4,5×5,6×6。這些產品通常使用一個6×6×h的長方體包裹包裝然后郵寄給客戶。因為郵費很貴，所以工廠要想方設法的減小每個訂單運送時的包裹數量。他們很需要有一個好的程序幫他們解決這個問題從而節省費用?，F在這個程序由你來設計。

【輸入】

輸入包括幾行，每一行代表一個訂單。每個訂單里的一行包括六個整數，中間用空格隔開，分別為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的可以占一個包裹，剩下的空由1?1的來補；

4?4的可以和2?2的搭配裝箱，如圖，塞入一個4?4的后還能塞5個2?2的。如果沒有5個2?2的，就用1?1的來補；

3?3的可以每四個打一捆，正好占用一個箱子。沒有4個3?3，就用2?2的 和?1?1的 來補，優先塞2?2的；

2?2的和1?1的優先拿去補別的產品，補滿了之后如果還有再用。

【參考代碼】

#include<stdio.h> int main() {int a,b,c,d,e,f; //六種產品的數量 int cnt; //最小包裹數int a_gap,b_gap; //剩余的空間數，a_gap，1*1空間，b_gap，2*2空間 while(scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f) && a||b||c||d||e||f){cnt=0;a_gap=0;b_gap=0;cnt+=f; //6*6的自己占一個包裹，包裹計數+f cnt+=e; //5*5的自己可以占一個包裹，包裹計數+e，每個剩余11個1*1，共e個a_gap+=11*e;cnt+=d; //4*4的自己也可以占一個包裹，包裹計數+d，每個剩余5個2*2，共計d個 b_gap+=5*d;cnt+=c/4; //3*3的裝箱 if(c%4!=0){cnt++;switch(c%4){case 1:b_gap+=5;a_gap+=7;break;case 2:b_gap+=3;a_gap+=6;break;case 3:b_gap+=1;a_gap+=5;default:break;}}if(b_gap>=b) //2*2的裝箱 {a_gap+=(b_gap-b)*2;}else{b-=b_gap;cnt+=b/9;if(b%9!=0){cnt++;a_gap+=36-4*b%9;}}if(a_gap<a) //1*1的裝箱 {a-=a_gap;cnt+=a/36;if(a%36!=0)cnt++;}printf("%d\n",cnt);}return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1226

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1226：装箱问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。