放牧代码和思想
专注自然语言处理、机器学习算法

POJ 1017 Packets 题解 《挑战程序设计竞赛(第2版)》练习题答案

2.2 一往直前!贪心法 其他

POJ 1017 Packets

有 1 * 1 到 6 * 6 的产品,最少用几个 6 * 6 的箱子装它们。

贪心策略是先装大的,再装小的,看我专门画的图就全明白了。生活常识,桶里先放碎石,再放沙,最后还可以装不少水。 6 * 6 和 5 * 5 以及 4 * 4 肯定独享一个箱子(不可能再放得下同规格的产品)。装了 4 * 4 和 3 * 3 的箱子还可以放 2 * 2 的产品,画个图就知道能放几个:

#include <iostream>
#include <cmath>
using namespace std;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int n, p1, p2, p3, p4, p5, p6, x , y;
	int space[4] = {0, 5, 3, 1}; // 一个箱子放入几个 3 * 3 后留下的缝隙可以放入几个 2 * 2
	while(true)
	{
		cin >> p1 >> p2 >> p3 >> p4 >> p5 >> p6;
		if(p1 == 0 && p2 == 0 && p3 == 0 && p4 == 0 && p5 == 0 && p6 == 0)
		{
			break;
		}
		// 第一次放“放不下第二个该型号”的型号,需要消耗n个箱子
		n = p4 + p5 + p6 + ceil(p3 / 4.0); // 对 3 * 3 的 package 来讲,四个刚好,否则向上取整
		// 计算 4 * 4 的型号和 3 * 3 的型号之间的缝隙可以放下多少个 2 * 2 的型号
		y = 5 * p4 + space[p3 % 4];
		// 2 * 2 的型号填入这些缝隙,如果填不下,再多消耗几个箱子
		if(p2 > y)
		{
			n += ceil((p2 - y) / 9.0); // 多出来的每9个刚好一个箱子
		}
		// 计算现在空了多少个 1 * 1 的位置
		x = 36 * n - 36 * p6 - 25 * p5 - 16 * p4 - 9 * p3 - 4 * p2;
		// 1 * 1 的型号填入这些缝隙,如果填不下,再多消耗几个箱子
		if(p1>x)
		{
			n += ceil((p1 - x) / 36.0);
		}
		cout << n << endl;
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1017 Packets 题解 《挑战程序设计竞赛(第2版)》练习题答案

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机