STEP BY STEP

POJ百练 - 1017:装箱问题

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

链接：http://poj.grids.cn/practice/1017
说实话这就是个简单的装箱子问题,很容易想清楚装箱子的过程,而且这个过程是满足贪心算法的,
所以只需要用代码模拟整个装箱子的过程即可,但是这样真的就足够了吗？？？
我刚开始就是用代码模拟这个手动过程了,虽然AC了,但是代码有150行左右,逻辑也显得过于复杂了,
得不偿失。。。整个过程是66的一个占一个箱子,55的也必须一个占一个箱子,但是需要补11个11的,
44的也是一个占一个箱子,但是需要补5个22的,如果22的不足够,则用11的代替,
33的4个占一个箱子,但是会有余数,可能余下1,2,3个33的箱子,这个时候必须非情况考虑,
1个33的需要和5个22的,7个11的组合,2个33的需要和3个22的,6个11的组合,
3个33的需要和1个22的,5个11的组合,最后考虑9个22的装一个箱子,多余的22用11的去填充尽量挤满一个箱子,
最后36个11的装一个箱子,余下的1*1的也必须占一个箱子。。。
这个过程说出来已经非常复杂了,更何况用代码写,我费了九牛二虎之力才写出来,WA了一次才AC了…

代码:

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <stdio.h>
int main()
{
    int one, two, three, four, five, six;
    int num = 0;
    while (scanf(“%d%d%d%d%d%d”, &one, &two, &three, &four, &five, &six) == 6)
    {
        if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
        {
            break;
        }
        num = six;
        num += five;
        if (one > five * 11)
        {
            one -= five * 11;
        }
        else
        {
            one = 0;
        }
        num += four;
        if (two > four * 5)
        {
            two -= four * 5;
        }
        else
        {
            if (one > four * 5 * 4 – two * 4)
            {
                one -= four * 5 * 4 – two * 4;
            }
            else
            {
                one = 0;
            }
            two = 0;
        }
        num += three / 4;
        three = three % 4;
        if (three == 1)
        {
            if (two > 5)
            {
                two -= 5;
                if (one > 7)
                {
                    one -= 7;
                }
                else
                {
                    one = 0;
                }
            }
            else
            {
                if (one > 27 – two * 4)
                {
                    one -= 27 – two * 4;
                }
                else
                {
                    one = 0;
                }
                two = 0;
            }
            ++num;
        }
        if (three == 2)
        {
            if (two > 3)
            {
                two -= 3;
                if (one > 6)
                {
                    one -= 6;
                }
                else
                {
                    one = 0;
                }
            }
            else
            {
                if (one > 18 – two * 4)
                {
                    one -= 18 – two * 4;
                }
                else
                {
                    one = 0;
                }
                two = 0;
            }
            ++num;
        }
        if (three == 3)
        {
            if (two > 1)
            {
                two -= 1;
                if (one > 5)
                {
                    one -= 5;
                }
                else
                {
                    one = 0;
                }
            }
            else
            {
                if (one > 9 – two * 4)
                {
                    one -= 9 – two * 4;
                }
                else
                {
                    one = 0;
                }
                two = 0;
            }
            ++num;
        }
        num += two / 9;
        two = two % 9;
        if (two)
        {
            if (one > 36 – two * 4)
            {
                one -= 36 – two * 4;
            }
            else
            {
                one = 0;
            }
            ++num;
        }
        num += one / 36;
        if (one % 36)
        {
            ++num;
        }
        printf(“%d\n”, num);
    }
    return 0;
}

这样的写法显然不好吧。。。首先,余下1,2,3个33时候需要填几个22的可以存储在数组里面,这样就可以不用写重复代码了,
如果再从整体考虑余下多少个格子,就不用用贪心算法模拟装箱子的过程了。。。
代码如下:

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
#include <stdio.h>
int main()
{
    int one, two, three, four, five, six;
    int num = 0;
    int twoPlace[4] = {0, 5, 3, 1};
    int remTwo, remOne;
    while (scanf("%d%d%d%d%d%d", &one, &two, &three, &four, &five, &six) == 6)
    {
        if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
        {
            break;
        }
        num = six + five + four + (three + 3) / 4;
        remTwo = four * 5 + twoPlace[three % 4];
        if (two > remTwo)
        {
            num += (two – remTwo + 8) / 9;
        }
        remOne = 36 * num – 36 * six – 25 * five – 16 * four – 9 * three – 4 * two;
        if (one > remOne)
        {
            num += (one – remOne + 35) / 36;
        }
        printf(“%d\n”, num);
    }
    return 0;
}

相关文章