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;
}
分享到:
相关推荐
pku部分题代码,不多,试一下怎么上传文件!
pku1000 pku1000程序 解题报告
pku经典题目解题报告 pku经典题目解题报告
PKU JudgeOnline FAQ 中文版 常见问题解答
pku1664源代码
benchmark (PKU-MMD) for continuous multi-modality 3D human action understanding and cover a wide range of complex human activities with well annotated information. PKU-MMD contains 1076 long video ...
8数码代码pku1077,300ms(哈希+广度搜索)
ppt word PKU 课件 五星级灰常强大
ACM代码 北大pku。 搞ACM的可以参考一下。代码还是挺规范的。有接近150道题目的代码。
PKU 2339 Rock, Scissors, Paper 源代码
pku acm 1469 COURSES 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
有一些代码是pku上的,希望大家看后给我留言,看看我的代码那里有问题??
北京大学pku2317 Questions and answers c++标程 文件名为2371.cpp
这是关于PKU上的题目分类 很详细 适合不同水平的童鞋们参考
PKU,POJ共301题源代码。1001 1002 1003 1004 1005 1006 1007 1008 1011 1012 1013 1014 1015 1017 1018 1019 1028 1032 1042 1046 1050 1061 1065
分词训练用的pku训练集,主要是说明相似度计算的样例数据。
我写的解题报告,关于度限制生成树的 网址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1639<br>题目:Picnic Planning 来源:East Central North America 2000
PKU的oj分类 可以通过分类进行练习~~~
pku acm 1042 贪心法