poj 1017 Packets 贪心

缘起

日常浪费生命 poj 1017 Packets

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
公司共有底面面积为1*1、2*2、3*3、4*4、5*5、6*6，高度同为H的六种产品，现在需要用最少的箱子打包，箱子
的底面面积为6*6，高度为H。

【输入】
每行都是一个样例. 包含6个数字，从左到右分别表示1*1、2*2、3*3、4*4、5*5、6*6 这6种箱子的个数.
输入结尾以6个零结束

【输出】
对于每个样例输出最小的箱子数量

【样例输入】
0 0 4 0 0 1 
7 5 1 0 0 0 
0 0 0 0 0 0 

【样例输出】
2 
1 

【限制】
1s

【来源】
Central Europe 1996

第一个样例是 4个3*3, 1个6*6，要用2个6*6进行运输，这是显然的. 第二个样例是7个1*1, 5个2*2, 1个3*3 ,只需要一个6*6即可. 当然，肯定不会只用面积大小来判断这么简单.

贪心. 

1
2
3
4
5
6自己占一个
5只能装一个,剩下的消耗1
4自己装一个, 剩下的消耗2和1
3最多装4个, 优先装3，如果装了1个3，则优先装2，最多装5个. 剩下的装1，如果装了2个3，则优先装2，最多装
3个，剩下装1，如果装了3个3，优先装2，最多装1个，剩下装1

下面的代码的思路就是这样. 对于5，它多出来的消耗1, 对于4，它多出来的消耗2，如果当2消耗完了的时候4可提供的尚未被消耗完, 则继续消耗1. 再考虑装3的方块. 则可以求出装3的方块剩余的空隙可以消耗2的，最后我们就得到了2和1剩下的个数. 倒数第二考虑2，最后考虑1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int a,b,c,d,e,f;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f), a||b||c||d||e||f)
	{
		int ans = f+e+d+c/4; // 装6和5和4和3, 剩下的就是e个里面1个5的方块, d个里面1个4的方块, 1个里面c%4个3的方块(如果c%4=0,则就是0个)
		a-=e*11; // e个里面装了1个5的方块消耗1
		b-=d*5; // d个里面装了1个4的方块消耗2
		if (b<0) // 如果有多, 则装4的方块可以继续消耗1
		{
			a-=(-b)*4; // 则多出来的可以消耗1
		}
		if (c%4)
		{
			ans++; // 装了c%4个3的方块
			c%=4; // 1个里面装了c个3的方块
			c = 4-c; // 还能装c个3, 1<=c<=3
			switch(c)
			{
			case 1:
				if (b>=1) // 如果2剩下>=1个,则可以消耗掉1个2,5个1
				{
					b-=1;
					a-=5;
				}
				else
				{
					a-=9; // 否则只能单纯消耗1
				}
				break;
			case 2:
				if (b>=3) // 如果2还够3个的话, 则消耗掉他们, a还可以消耗6个
				{
					b-=3;
					a-=6;
				}
				else if(b>=2)
				{
					b=0;
					a-=10;
				}
				else if (b>=1)
				{
					b = 0;
					a-=14;
				}
				else // 单纯消耗1
				{
					a-=18;
				}
				break;
			case 3:
				if (b>=5) // 如果2还够3个的话, 则消耗掉他们, a还可以消耗6个
				{
					b-=5;
					a-=7;
				}
				else if(b>=4)
				{
					b-=4;
					a-=11;
				}
				else if (b>=3)
				{
					b -=3;
					a-=15;
				}
				else if (b>=2)
				{
					b -=2;
					a-=19;
				}
				else if (b>=1)
				{
					b -=1;
					a-=23;
				}
				else
				{
					a-=27;
				}
				break;
			}
		}
		if (b>0) // 至此，得到了1和2剩余的个数a和b
		{
			ans+=b/9; //一个6可以装9个2
			if (b%9)
			{
				ans++;
				b%=9;
				b=9-b; // 则剩下一个还可以装b个2的盒子
				a-=b*4; // 继续消耗1
			}
		}
		if (a>0) // 如果1还有多
		{
			ans+=a/36;
			if (a%36)
			{
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 84kB
Length 1600
Lang C++
Submitted 2019-08-24 21:19:45
Shared
RemoteRunId 20797182