pku1017

pku 1017   http://poj.org/problem?id=1017  解答过程

 

 

下面是最傻的方法, 逐一处理6*6    5*5     4*4  ...     进行详细而繁杂的讨论

 

#include<iostream>
using namespace std;

int main(){
	int p1, p2, p3, p4, p5, p6;
	int count = 0;
	while(1){
		cin>>p1>>p2>>p3>>p4>>p5>>p6;
		if(p1 == 0 && p2 == 0 && p3 == 0 && p4 == 0 && p5 == 0 && p6 == 0 ){
			break;
		}
		count = 0;
		//求cout
		int num2, num1;
		count += p6;					//处理6*6
		p6 = 0;
		while(p5 > 0){					//处理5*5
			p5 --;
			count ++;
			num1 = 11;
			while(p1 > 0 && num1 > 0){
				p1 --;
				num1 --;
			}
		}
		while(p4 > 0){					//处理4*4
			p4 --;
			count ++;
			int num2 = 5; //temp4表示还可以放5个2
			while(p2 > 0 && num2 > 0){
				p2 --;
				num2 --;
			}
			while(num2 > 0 && p1 > 0){
				num2 --;
				p1 --;
				p1 --;
			}
		}
		if(p3 > 0){						//处理3*3
			count += p3 / 4;
			p3 = p3 % 4; //还剩下的3*3的个数
			if(p3 != 0){
				count ++;//把剩下的3*3装入一个包裹里面, 再处理剩下的空位
				if(p3 == 1){
					num2 = 5; 
					while(p2 > 0 && num2 >0){
						p2 --;
						num2 --;
					}
					num1 = 7 + num2 * 2;
					while(p1 > 0 && num1 > 0){
						p1 --;
						num1 --;
					}
				}
				if(p3 == 2){
					num2 = 3; 
					while(p2 > 0 && num2 >0){
						p2 --;
						num2 --;
					}
					num1 = 6 + num2 * 2;
					while(p1 > 0 && num1 > 0){
						p1 --;
						num1 --;
					}
				}
				if(p3 == 3){
					num2 = 1; 
					while(p2 > 0 && num2 >0){
						p2 --;
						num2 --;
					}
					num1 = 5 + num2 * 2;
					while(p1 > 0 && num1 > 0){
						p1 --;
						num1 --;
					}
				}
			}
		}//end处理3*3
		if(p2 > 0){						//处理2*2
			count += p2 / 9;
			p2 = p2 % 9; //还剩下的2*2的个数
			if(p2 != 0){
				count ++;
				num1 = (9 - p2) * 4;
				while(p1 > 0 && num1 > 0){
					p1 --;
					num1 --;
				}
			}
		}//end处理2*2
		if(p1 > 0){						//处理1*1
			count += p1 / 36;
			if(p1 % 36 != 0)
				count ++;
		}
		cout<<count<<endl;
		
	}
	system("pause");
	return 0;
}

 

 

上面的方法太复杂, 讨论的方向过多, 很容易出错

 

 

 

如果加入更多的数学分析, 可以得出更简单的算法, 因为其中很多while是可以直接算出来的

 

#include<iostream>
using namespace std;

int main(){
	int p1, p2, p3, p4, p5, p6;
	int count = 0, num1 = 0, num2 = 0;//count为所需要的包裹的总数  num1和num2为余下的1*1 和2*2的空位
	int left2[4] = {0, 5, 3, 1};//4个值分别对应3*3的个数对4求余后, 还余下的2*2的空位
	while(1){
		cin>>p1>>p2>>p3>>p4>>p5>>p6;
		if(p1 == 0 && p2 == 0 && p3 == 0 && p4 == 0 && p5 == 0 && p6 == 0 ){
			break;
		}	
		count = p4 + p5 + p6; //每个4*4 和5*5 、6*6 都会占一个包裹
		count += (p3 + 3) / 4;//3*3会占的包裹数，  加3是为了向上取整
		num2 = p4 * 5 + left2[(p3 % 4)]; //剩余的2*2的空位为每个装4*4的包裹中余下的5个, 以及3*3对4求余后的3*3所装的一个包裹中余下的
		if(p2 > num2){//还有2*2没有装入包裹
			count += (p2 - num2 + 8) / 9;//为2*2单独新开的包裹数
		}
		num1 = count * 36 - (p6 * 36 + p5 * 25 + p4 * 16 + p3 * 9 + p2 * 4);//用所有包裹的总体积 减去 p2~p6所占总体积, 求得1*1空位  
		if(p1 > num1){//还有1*1没有装入包裹
			count += (p1 - num1 + 35) / 36;
		}
		cout<<count<<endl;
	}
	return 0;
}