問題描述

輸入數(shù)據(jù)

輸出要求

       除了輸入的最后一行 6 個(gè) 0 以外，輸入文件里每一行對應(yīng)著輸出文件的一行，每一行輸出一個(gè)整數(shù)代表對應(yīng)的訂單所需的最小包裹數(shù)。

輸入樣例

0 0 4 0 0 17 5 1 0 0 00 0 0 0 0 0
輸出樣例
21
解題思路
        這個(gè)問題描述得比較清楚，我們在這里只解釋一下輸入輸出樣例：共有兩組有效輸入，第一組表示有 4 個(gè) 3*3 的產(chǎn)品和一個(gè) 6*6 的產(chǎn)品，此時(shí) 4 個(gè) 3*3 的產(chǎn)品占用一個(gè)箱子，另外一個(gè) 6*6 的產(chǎn)品占用 1 個(gè)箱子，所以箱子數(shù)是 2；第二組表示有 7 個(gè) 1*1 的產(chǎn)品， 5 個(gè) 2*2的產(chǎn)品和 1 個(gè) 3*3 的產(chǎn)品，我們可以把他們統(tǒng)統(tǒng)放在一個(gè)箱子中，所以輸出是 1。分析六個(gè)型號的產(chǎn)品占用箱子的具體情況如下：        （1.）6*6 的產(chǎn)品每個(gè)會占用一個(gè)完整的箱子，并且沒有空余空間；        （2.）5*5 的產(chǎn)品每個(gè)占用一個(gè)新的箱子，并且留下 11 個(gè)可以盛放 1*1的產(chǎn)品的空余空間；        （3.）4*4 的產(chǎn)品每個(gè)占用一個(gè)新的箱子，并且留下 5 個(gè)可以盛放 2*2 的產(chǎn)品的空余空間；        （4.）3*3 的產(chǎn)品情況比較復(fù)雜， 首先 3*3 的產(chǎn)品不能放在原來盛有 5*5 或者 4*4 的箱子中， 那么必須為 3*3 的產(chǎn)品另開新的箱子， 新開的箱子數(shù)目等于 3*3 的產(chǎn)品的數(shù)目除以4 向上取整； 同時(shí)我們需要討論為 3*3 的產(chǎn)品新開箱子時(shí)， 剩余的空間可以盛放多少 2*2 和1*1 的產(chǎn)品（這里如果有空間可以盛放 2*2 的產(chǎn)品，我們就將它計(jì)入 2*2 的空余空間，等到2*2 的產(chǎn)品全部裝完，如果還有 2*2 的空間剩余，再將它們轉(zhuǎn)換成 1*1 的剩余空間）。我們可以分情況討論為 3*3 的產(chǎn)品打開的新箱子中剩余的空位，共為四種情況：
                           第一種， 3*3 的產(chǎn)品的數(shù)目正好是 4 的倍數(shù)，所以沒有空余空間；
                           第二種， 3*3 的產(chǎn)品數(shù)目是 4 的倍數(shù)加 1，這時(shí)還剩 5 個(gè) 2*2 的空位和 7 個(gè) 1*1 的空位；
                           第三種， 3*3 的產(chǎn)品數(shù)目是 4 的倍數(shù)加 2，這時(shí)還剩 3 個(gè) 2*2 的空位和 6 個(gè) 1*1 的空位；
                           第四種， 3*3 的產(chǎn)品數(shù)目是 4 的倍數(shù)加 3，這時(shí)還剩 1 個(gè) 2*2 的空位和 5 個(gè) 1*1 的空位；
       （5.）處理完 3*3 的產(chǎn)品，就可以比較一下剩余的 2*2的空位和 2*2 產(chǎn)品的數(shù)目，如果產(chǎn)品數(shù)目多，就將 2*2 的空位全部填滿，再為 2*2 的產(chǎn)品打開新箱子，同時(shí)計(jì)算新箱子中 1*1 的空位，如果剩余空位多，就將 2*2 的產(chǎn)品全部填入 2*2的空位，再將剩余的 2*2 的空位轉(zhuǎn)換成 1*1 的空位；       （6.）最后處理 1*1 的產(chǎn)品，比較一下 1*1的空位與 1*1 的產(chǎn)品數(shù)目，如果空位多，將 1*1 的產(chǎn)品全部填入空位，否則，先將 1*1 的空位填滿，然后再為 1*1 的產(chǎn)品打開新的箱子。
理不太清楚的大家在草稿紙上畫一下就清楚了。
參考程序
#include <iostream>using namespace std;int main(){	int N,a,b,c,d,e,f,y,x; 	int u[4]={0,5,3,1}; 	//數(shù)組u表示上述3*3中對應(yīng)的剩余2*2空位個(gè)數(shù)的四種情況  	while(true){	 	cin>>a>>b>>c>>d>>e>>f;	 	if(!a && !b && !c && !d && !e && !f){	 		break;	 	}	 	N = f+e+d+(c+3)/4;	 	//這里有一個(gè)小技巧(c+3)/4 正好等于 c 除以 4 向上取整的結(jié)果,下同	 	y = 5*d + u[c%4];	 	if(b > y){		 	//2*2需新開箱 	 		N += (b-y+8)/9;	 	}	 	//計(jì)算剩余箱子的空間，總的減去占用的 	 	x = 36*N-36*f-25*e-16*d-9*c-4*b;	 	if(a > x){	 		//1*1需新開箱	 		N += (a-x+35)/36;	 	}	 	cout<<N<<endl;	 }	return 0;}