题目链接

Packets POJ - 1017

思路

贪心能放大的放大的，3 × 3 的比较特殊， 这个题一遍写对还是不容易的。

时间复杂度

$$ O(1) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int a1, a2, a3, a4, a5, a6;
    while (scanf("%d%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5, &a6)
    , a1 + a2 + a3 + a4 + a5 + a6) {
        int ans = a6;
        if (a5) {
            ans += a5;
            int r = a5 * (6 * 6 - 5 * 5);
            a1 -= min(a1, r);
        }
        if (a4) {
            ans += a4;
            int r = a4 * (6 * 6 - 4 * 4);
            int k = min(a2, r / (2 * 2));
            a2 -= k;
            r -= k * (2 * 2);
            a1 -= min(a1, r);
        }
        if (a3) {
            ans += a3 / 4;
            a3 %= 4;
            if (a3) {
                ans++;
                if (a3 == 3) {
                    int r = 3 * 3;
                    int k = min(a2, 1);
                    a2 -=k;
                    r -= k * 2 * 2;
                    a1 -= min(a1, r);
                } else if (a3 == 2) {
                    int r = 3 * 3 * 2;
                    int k = min(a2, 3);
                    a2 -= k;
                    r -= k * 2 * 2;
                    a1 -= min(a1, r);
                } else if (a3 == 1) {
                    int r = 3 * 3 * 3;
                    int k = min(a2, 5);
                    a2 -= k;
                    r -= k * 2 * 2;
                    a1 -= min(a1, r);
                }
            }
        }
        if (a2) {
            ans += a2 / 9;
            a2 %= 9;
            if (a2) {
                ans++;
                int r = 36 - a2 * (2 * 2);
                a1 -= min(a1, r);
            }
        }
        if (a1) {
            ans += a1 / 36;
            a1 %= 36;
            if (a1) {
                ans++;
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}