poj 1017 Packets

知识点：贪心

解题报告

#include <cstdio>
#include <algorithm>

int square[7];

// 解法：每次都先放最大

int solve() {
  int res = 0;
  // 6x6 直接成一块
  res += square[6];
  // 5x5 先成一块，再补 1x1
  res += square[5];
  square[1] -= 11 * square[5];
  // 4x4 先成一块，然后再补 2x2, 1x1
  res += square[4];
  int remain = 20 * square[4];
  while(remain != 0) {
    if (square[2] > 0) {
      square[2]--;
      remain-=4;
    } else if (square[1] > 0) {
      square[1]--;
      remain--;
    } else {
      break;
    }
  }

  // 3x3 优先使用 3x3 自成一块，然后才是 2x2, 1x1
  res += square[3] / 4;
  square[3] %= 4;
  if (square[3] > 0) {
    res++;
    int a;
    // 陷阱：2x2 在补的时候有数量限制！分情况
    switch(square[3]) {
      case 1:
      a = 5;
      remain = 27;
      break;
      case 2:
      a = 3;
      remain = 18;
      break;
      case 3:
      a = 1;
      remain = 9;
      break;
    }
    while(remain && a && square[2] > 0) {
      remain-=4;
      square[2]--;
      a--;
    }
    square[1]-=remain;
  }

  // 如果 2x2 还有剩，自成一块，多出来的再和 1x1 继续拼
  if (square[2] > 0) {
    res += square[2] / 9;
    square[2] %=9;
    if (square[2] > 0) {
      res++;
      square[1] -= 36 - 4 * square[2];
    }
  }
  // 如果 1x1 还有剩，只能自成一块
  if (square[1] > 0) {
    res += square[1] / 36;
    if (square[1] % 36) res++;
  }
  return res;
}

int main() {
  int i;
  while(1) {
    for(i=1;i<=6;i++) {
      scanf("%d", &square[i]);
    }
    if (square[1]+square[2]+square[3]+square[4]+square[5]+square[6] == 0) {
      break;
    }
    printf("%d\n", solve());
  }
  return 0;
}