UVa 311 Packets

題意：
　　本題共有1x1,2x2,3x3,4x4,5x5,6x6共6種箱子數個(每行Input代表各個的數量)，而它們的高度均一樣，所以本題只考慮平面，而題目問的是，有一個大箱子的大小為6x6，如何使用最少數量的大箱子將上述的6種箱子包裝起來。

想法：

1. 6x6：1個6x6剛好裝滿一個大箱子
2. 5x5：一個5x5搭配11個1x1
3. 4x4：一個4x4搭配5個2x2，如果2x2不夠改用4個1x1代替
4. 3x3：要分別討論1~3個3x3 與2x2和1x1搭配的數量
5. 2x2與1x1：如果有剩下再放進大箱子

	#include <cstdio>
	using namespace std;
	void parcel(int &box,int num[],int &space,int w);
	int main()
	{
	int num[7];
	while(scanf("%d %d %d %d %d %d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6])){
	int i=1;
	for(;i<=6;i++)
	if(num[i]!=0) break;
	if(i==7) break;
	int box=num[6]+num[5]+num[4];
	num[1]-=11*num[5]; //一個5x5搭配11個1x1
	num[2]-=5*num[4]; //一個4x4搭配5個2x2(如果2x2不夠的情況最底下會考慮)
	box+=(num[3]/4); if(num[3]%4) box++;
	switch(num[3]%4){ //3x3情況要特別討論
	case 0: break;
	case 1:
	num[2]-=5;
	num[1]-=7;
	break;
	case 2:
	num[2]-=3;
	num[1]-=6;
	break;
	case 3:
	num[2]-=1;
	num[1]-=5;
	break;
	}
	if (num[2]>0){ //如果2x2還有剩
	box+=num[2]/9; if(num[2]%9) box++;
	num[1]-=(36-(num[2]%9)*4);
	}
	else if (num[2]<0)
	num[1]-=(-num[2])*4; //將不夠的2x2用4個1x1來補
	if (num[1]>0){ //如果1x1還有剩
	box+=(num[1]/36); if(num[1]%36) box++;
	}
	printf("%d\n",box);
	}
	return 0;
	}

view raw [UVa] 311 Packets.cpp hosted with ❤ by GitHub