Teacher 2008-9-6 00:45
北大pku poj 1017 Packets解题报告源代码
题目地址: [url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1017[/url]
-----代码仅供参考学习-----
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 13651 Accepted: 4583
Description
A factory produces products packed in square packets of the same height h and of the sizes 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. These products are always delivered to customers in the square parcels of the same height h as the products have and of the size 6*6. Because of the expenses it is the interest of the factory as well as of the customer to minimize the number of parcels necessary to deliver the ordered products from the factory to the customer. A good program solving the problem of finding the minimal number of parcels necessary to deliver the given products according to an order would save a lot of money. You are asked to make such a program.
Input
The input file consists of several lines specifying orders. Each line specifies one order. Orders are described by six integers separated by one space representing successively the number of packets of individual size from the smallest size 1*1 to the biggest size 6*6. The end of the input file is indicated by the line containing six zeros.
Output
The output file contains one line for each line in the input file. This line contains the minimal number of parcels into which the order from the corresponding line of the input file can be packed. There is no line in the output file corresponding to the last ``null'' line of the input file.
Sample Input
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
Sample Output
2
1
Source
一看Total Submissions: 13651 Accepted: 4583 又是一道水题 。基本的数学问题，只要思路清晰，一下就AC了。
首先对每个 6 * 6 的产品一定会单独用一个 PACKETS 而且不会余下格子。
对每个 5 * 5的产品也一定要单独用一个PACKETS 且多出的格子只可能装11个 1 * 1的；
对 4 * 4的产品也一定要单独用一个PACKETS 且多出的格子只可能装 5个 2 * 2
（ 因为 2 * 2的一定可以化为4个 1 * 1， 所以能转为2 * 2就不转为 1 * 1 ）
对 3 * 3的产品也一定会最多4个单独用一个PACKETS， 所以计算出 / 4的商和余数就分别
会是 要的PACKETS数和多出的格子，注意细节的考虑。
2 * 2和 1 * 1就比较简单了，依次类推就OK了。
下面是代码
/*-------------------------------------
FileName: 1017.cpp
Descrtption: Packets
Author: Yang Li
Date: 07.05.2008
Version: 1.0
--------------------------------------
偶的代码里面都用了大量的空行和空格,
看起来比较多,主要是为了养成良好的习惯,
其实并不多的 100行只等于60行左右吧
--------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int Num[6]; //用来记录各种类型产品的数量
int Res[2]; //余下的 1 * 1的空格和 2 * 2的空格。
int n;
void Slove ( )
{
n += Num[5] + Num[4] + Num[3]; //对 6 * 6， 5 * 5， 4 * 4 没种一个产品必须一个PACTETS
if ( Num[2] > 0 ) //对 3 * 3的每 4个产品要一个PACKETS
n += ( Num[2] - 1 ) / 4 + 1;
Res[0] = Num[4] * 11; // 加上余下的1 * 1空格
Res[1] = Num[3] * 5; // 加上2 * 2的空格数
int rel = Num[2] % 4; // 装了 3 * 3后 未装满的那个PACKETS余下的格子
if ( rel == 1 ) // 以下都是再个中情况下 最多能余下的 1 * 1 和2 * 2的格子
{
Res[0] += 7;
Res[1] += 5;
}
else if ( rel == 2 )
{
Res[0] += 6;
Res[1] += 3;
}
else if ( rel == 3 )
{
Res[0] += 5;
Res[1] += 1;
}
rel = Res[1] - Num[1]; // 看余的的2 * 2比需要装的多不
if ( rel >= 0 ) // 多的话全部转化为1 * 1的
Res[0] += rel * 4;
else // 另外找包裹来装 2 * 2的 同时计算余下的1 * 1
{
rel = -rel;
n += ( rel - 1 ) / 9 + 1;
if ( rel % 9 )
Res[0] += 36 - ( rel % 9 ) * 4;
}
rel = Res[0] - Num[0]; // 同 2 * 2 一个原理
if ( rel >= 0 )
printf ( "%d\n", n );
else
{
rel = -rel;
n += ( rel - 1 ) / 36 + 1;
printf ( "%d\n", n );
}
return ;
}
int main ( )
{
while ( 1 )
{
int flag = 0;
n = 0;
Res[1] = Res[0] = 0;
for ( int i = 0; i < 6; i++ )
{
scanf ( "%d", &Num );
if ( Num )
flag = 1;
}
if ( !flag )
break;
Slove ( );
}
return 0;
}