UVaOJ 1587 - Box

问题描述

相关说明：本题为《算法竞赛入门经典（第2版）》习题 3-10, 借助这本书入门的读者不要被网上一些用到运算符重载以及自定义排序的题解给吓到了，找到解决问题的思路更加关键。下面题解中用到的 STL 容器，也可以使用数组来代替。

解法一：排序 + 分类讨论

为了简化情况，我们每次输入宽 w 和高 h 时都处理下，确保 w >= h 成立（在更优的解法二中会约束成另一种情况）。

如果输入的六条木板能够组成长方体，那么它们的宽 w 和高 h 一定满足以下情况：这些木板 pallets 能够表示成三对形状相同的木板（上下、左右、前后） —— 非对称面的木板形状也有可能相同，但我们将形状相同的木板放在一起，那么几种木板的数量比例无非是 6 / 4:2 / 2:2:2. 无论如何，某种类型的木板的数量都会是 2 的倍数。因此我们可以首先进行一次筛选，不满足则直接输出 IMPOSSIBLE. 进而将情况简化成：判断 3 对形状相同的木板能否组成长方体。

为了方便理解，我们用一个实际输入来模拟后面的步骤。假定这三对木板的宽和高分别是：5 4, 5 3, 4 3. （再次注意 w>=h 始终成立）。我们执行判断的逻辑是：

取第一对木板（如 5 4 木板），它的宽高记录下来，用来给第二对木板做匹配；
取第二对木板（如 5 3 木板），与第一块的宽高对比，如果找到某个一致的长度（5），说明此时可以拼在一起，这时候剩下的两个长度（此时为 4 和 3）则可以作为第三块木板的一种解决方案；如果找不到一致的长度，直接 IMPOSSIBLE.
取最后一对木板，如果它的宽和高能够和第 2 步找到的某个解决方案匹配，则说明 POSSIBLE.

P.S: 在执行第 2 步时，可能可以找到两个解决方案 —— 比如当第一对木板和第二对木板的形状都为 5 3 时，第三块的木板形状可以是 5 5 或者 3 3, 因此在模拟时不能忽略这种情况。

注意：在下面实际实现的代码中，由于用了 set 这种顺序数据结构来存储某种形状出现的次数，因此对于同样情况的输入，取第一、二、三对木板的顺序是一定的。比如在上面举例的情况中，取出的第一对木板的形状一定是 4 3, 第二块木板的形状一定是 5 3, 最后一对木板的形状是 5 4. 在第 2 步寻找解决方案 solution 时，只要保证插入的长度顺序依旧是前者大于后者 w >= h ，则在最后一步比较时就不需要分类讨论了，这也是对数据进行一定处理所带来的好处。

#include <bits/stdc++.h>

using namespace std;

int main() {
  const int LINE_NUMBER = 6;
  int w, h;
  map<pair<int, int>, int> pallets;
  while (true) {
    pallets.clear();
    for (int i = 0; i < LINE_NUMBER; ++i) {
      if (!(cin >> w >> h)) return 0;
      if (w < h) swap(w, h);
      pallets[pair<int, int>(w, h)]++;
    }

    bool possible = true;
    for (auto pallet : pallets)
      if (pallet.second % 2 != 0) possible = false;

    if (!possible) {
      cout << "IMPOSSIBLE" << endl;
      continue;
    }

    int pallet_id = 0;
    vector<pair<int, int>> solution;
    for (auto pallet : pallets)
      for (int i = 0; i < pallet.second; i += 2) {
        pallet_id += 1;
        w = pallet.first.first;
        h = pallet.first.second;
        if (pallet_id == 1) {
          solution.push_back(pair<int, int>(w, h));
        } else if (pallet_id == 2) {
          if (w == solution[0].first)
            solution.push_back(pair<int, int>(h, solution[0].second));
          if (h == solution[0].second)
            solution.push_back(pair<int, int>(w, solution[0].first));
          if (solution.size() == 1) possible = false;
        } else if (possible) {
          possible = false;
          for (int i = 1; i < solution.size(); ++i)
            if (solution[i].first == w && solution[i].second == h)
              possible = true;
        }
      }
    cout << (possible ? "POSSIBLE" : "IMPOSSIBLE") << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {

const int LINE_NUMBER = 6;

int w, h;

map<pair<int, int>, int> pallets;

while (true) {

pallets.clear();

for (int i = 0; i < LINE_NUMBER; ++i) {

if (!(cin >> w >> h)) return 0;

if (w < h) swap(w, h);

pallets[pair<int, int>(w, h)]++;

}

bool possible = true;

for (auto pallet : pallets)

if (pallet.second % 2 != 0) possible = false;

if (!possible) {

cout << "IMPOSSIBLE" << endl;

continue;

}

int pallet_id = 0;

vector<pair<int, int>> solution;

for (auto pallet : pallets)

for (int i = 0; i < pallet.second; i += 2) {

pallet_id += 1;

w = pallet.first.first;

h = pallet.first.second;

if (pallet_id == 1) {

solution.push_back(pair<int, int>(w, h));

} else if (pallet_id == 2) {

if (w == solution[0].first)

solution.push_back(pair<int, int>(h, solution[0].second));

if (h == solution[0].second)

solution.push_back(pair<int, int>(w, solution[0].first));

if (solution.size() == 1) possible = false;

} else if (possible) {

possible = false;

for (int i = 1; i < solution.size(); ++i)

if (solution[i].first == w && solution[i].second == h)

possible = true;

}

cout << (possible ? "POSSIBLE" : "IMPOSSIBLE") << endl;

}

return 0;

}

这种解法是一些读者第一反应能够想到的做法，即当作大模拟题去逐步拼接这个长方体。其中如果能保证 w >= h 条件成立，将减少许多的比较和讨论。但我们也提到：在维护 set 数据结构的时候，它将会自动对里面的元素 a 和 b 排序，对于每类形状的木板而言，优先保证 a.w <= b.w ，然后保证 a.h <= b.h. 可以感受到，这与前面的单个木板内 w >= h 性质的结合不是那么自然。因此我们还有一种更强的排序情况，利用它能进一步减少需要被讨论的情况，将此模拟题简化成一个找规律快速验证的题。

解法二：排序 + 分类讨论（优化版）

在上面的解法中，我们知道 STL 容器的排序规律默认是值小的在前面。因此我们可以在一开始输入 w 和 h 时，就做一些处理，保证 w <= h. 这样我们最终能够得到一个始终递增的 pallets 数据结构，注意到我们这次使用了 vector 代替 set 来作为木板对象的容器，因此需要手动调动 sort 算法对里面的 pair 数据进行排序，默认逻辑即满足要求；另外在考虑能否找出 3 对木板时，判断的逻辑也更加简单。

同样地，假设问题简化后，这三对木板的宽和高分别是：5 4, 5 3, 4 3.

经过排序后，我们按次序得到的三对木板的长宽分别是：3 4, 3 5, 4 5.

模拟一下，很容易找到规律，如果这三对严格排序后的木板能组成长方形，一定满足：

排在第一对的木板的 first 与排在第二对木板的 first 长度一致；
排在第二对的木板的 second 与排在第三对木板的 second 长度一致；
剩下地，则有排在第一对的木板的 second 与排在第三对木板的 first 长度一致。

感受一下，这是在维护数据时严格保证顺序，所能带来的好处。

#include <bits/stdc++.h>

using namespace std;

int main() {
  const int LINE_NUMBER = 6;
  int w, h;
  vector<pair<int, int>> pallets;
  while (true) {
    pallets.clear();
    for (int i = 0; i < LINE_NUMBER; ++i) {
      if (!(cin >> w >> h)) return 0;
      if (w > h) swap(w, h);
      pallets.push_back(pair<int, int>(w, h));
    }

    sort(pallets.begin(), pallets.end());

    bool possible = true;
    for (int i = 0; i < LINE_NUMBER; i += 2)
      if (pallets[i] != pallets[i + 1]) possible = false;

    cout << (possible && (pallets[0].first == pallets[2].first &&
                          pallets[0].second == pallets[4].first &&
                          pallets[2].second == pallets[4].second)
                 ? "POSSIBLE"
                 : "IMPOSSIBLE")
         << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {

const int LINE_NUMBER = 6;

int w, h;

vector<pair<int, int>> pallets;

while (true) {

pallets.clear();

for (int i = 0; i < LINE_NUMBER; ++i) {

if (!(cin >> w >> h)) return 0;

if (w > h) swap(w, h);

pallets.push_back(pair<int, int>(w, h));

}

sort(pallets.begin(), pallets.end());

bool possible = true;

for (int i = 0; i < LINE_NUMBER; i += 2)

if (pallets[i] != pallets[i + 1]) possible = false;

cout << (possible && (pallets[0].first == pallets[2].first &&

pallets[0].second == pallets[4].first &&

pallets[2].second == pallets[4].second)

? "POSSIBLE"

: "IMPOSSIBLE")

<< endl;

}

return 0;

}

LINE_NUMBER = 6

while True:
    pallets = []
    try:
        for i in range(LINE_NUMBER):
            w, h = input().split()
            pallets.append((h, w) if w > h else (w, h))
        pallets = sorted(pallets)
        possible = True
        for i in range(0, LINE_NUMBER, 2):
            if pallets[i] != pallets[i + 1]:
                possible = False
        print("POSSIBLE" if possible and
              (pallets[0][0] == pallets[2][0]
               and pallets[0][1] == pallets[4][0]
               and pallets[2][1] == pallets[4][1]) else "IMPOSSIBLE")

    except EOFError:
        break

LINE_NUMBER = 6

while True:

pallets = []

try:

for i in range(LINE_NUMBER):

w, h = input().split()

pallets.append((h, w) if w > h else (w, h))

pallets = sorted(pallets)

possible = True

for i in range(0, LINE_NUMBER, 2):

if pallets[i] != pallets[i + 1]:

possible = False

print("POSSIBLE" if possible and

(pallets[0][0] == pallets[2][0]

and pallets[0][1] == pallets[4][0]

and pallets[2][1] == pallets[4][1]) else "IMPOSSIBLE")

except EOFError:

break

AOAPC II UVaOJ 字符串