总时间限制: 1000ms 内存限制: 65536kB

描述

一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1×1, 2×2, 3×3, 4×4, 5×5, 6×6。这些产品通常使用一个 6×6×h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。

输入

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空格隔开，分别为1×1至6×6这六种产品的数量。输入文件将以6个0组成的一行结尾。

输出

除了输入的最后一行6个0以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。

样例输入

  1. 0 0 4 0 0 1 
  2. 7 5 1 0 0 0 
  3. 0 0 0 0 0 0

样例输出

  1. 2 
  2. 1

思路

由于产品和集装箱的高度都是一样的，我们可以把这个问题转换成“圈地运动”那样的面积问题。

为了让成本最低，我们倾向于先把大的产品塞满集装箱，有剩余空间再塞尺寸小的产品。如果不够再开一个新的集装箱。

画图可知：

  • 6×6的产品一次性就占满了一个集装箱，没有面积剩余；
  • 5×5的产品放进集装箱后，还剩下11个 1×1 的面积；
  • 4×4的产品放进集装箱后，还剩下5个 2×2 的面积(当然也可以塞20个 1×1的产品，但我们倾向于先塞大的)；

  • 3×3的产品放进集装箱后，会出现以下三种情况：

    1. 一个集装箱能塞下4个 3×3 的产品，如果工厂生产的 3×3 产品正好是4的倍数，那么集装箱正好塞满。
    2. 如果 3×3 的产品 mod4 = 1，那集装箱还能塞下5个 2×2 的产品 和 7个 1×1 的产品。
    3. 如果 3×3 的产品 mod4 = 2，那集装箱还能塞下3个 2×2的产品 和 6个 1×1 的产品。
    4. 如果 3×3 的产品 mod4 = 3，那集装箱还能塞下1个 2×2的产品 和 5个 1×1 的产品。
  • 因为一个集装箱能装下9个 2×2 的产品，当所有空位都塞完后，还剩有 2×2 的产品，就得新开一个集装箱。计算公式是 sum += (left22 + 8）/ 9.
  • 最后是计算 1×1 的产品

代码

  1. #include<iostream>
  2. using namespace std;
  4. int main() {
  5.     int a, b, c, d, e, f;
  6.     int box11, box22;
  7.     while(true) {
  8.         scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
  9.         if(a + b + c + d + e + f == 0)
  10.             break;
  11.         int sum = f + d + e + (c + 3)/4; // 需要的总集装箱个数
  13.         box22 = d * 5;    // 5x5 的产品还能多装5个 2x2 的产品
  14.         // 判断 3x3 的产品有几个
  15.         if(c % 4 == 3)  box22 += 1;
  16.         else if(c % 4 == 2)  box22 += 3;
  17.         else if(c % 4 == 1)  box22 += 5;
  19.         if(box22 < b) // 如果把现有的空位都塞完了, 还剩有 2x2 的产品
  20.             sum += ((b - box22) + 8) / 9;
  21.         box11 = 36*sum -  36*f - 25*e - 16*d - 9*c - 4*b;
  22.         if(box11 < a) 
  23.             sum += ((a - box11) + 35) / 36;
  24.         printf("%d\n", sum);
  25.     }
  27.     return 0;
  28. }