题目解析

我们有 $n$ 个矩形印章，每个印章尺寸为 $w_i \times h_i$。
我们可以将它们任意放置在无限网格上（允许重叠），最终所有黑色格子形成若干连通区域。
目标是最小化所有连通区域周长的总和。

关键观察

1. 重叠可以减小总周长
   如果两个矩形有重叠部分，它们会合并成一个连通区域，从而减少总周长（因为内部公共边不再计入边界）。

2. 最优策略：将所有矩形对齐放置
   将所有矩形的一个角（例如左下角）放在同一个点上。这样所有矩形都堆叠在同一个矩形区域 $[0, W] \times [0, H]$ 中，其中
   $W = \max(w_i)$，$H = \max(h_i)$。
   此时整个黑色区域恰好就是这个大矩形（因为所有小矩形都被包含在内），并且它是一个单连通块。

3. 周长计算
   该大矩形的周长为 $2(W + H)$。
   由于所有矩形都被包含在其中，这个周长就是所有黑色格子组成的外边界长度。内部重叠部分的边界不计入周长（因为被内部填充）。

4. 为什么这是最优的？

   • 任何放置方案中，所有矩形的宽度至少为 $W$（最大值），高度至少为 $H$（最大值）。
   • 无论怎样排列，黑色区域的整体外轮廓至少需要覆盖宽度 $W$ 和高度 $H$，因此最小可能的周长下界就是 $2(W + H)$。
   • 上述对齐放置恰好达到这个下界，所以是最优解。

结论

答案仅取决于所有印章的最大宽度 $w_{\max}$ 和最大高度 $h_{\max}$：

算法步骤

1. 读入测试用例数 $t$。
2. 对每个测试用例：
   • 读入 $n$。
   • 遍历所有矩形，记录最大宽度 maxw 和最大高度 maxh。
   • 输出 $2 \times (\text{maxw} + \text{maxh})$。

时间复杂度：$O(\sum n)$，空间复杂度：$O(1)$。

示例验证

以题目第一个样例：

5
1 5
2 4
3 3
4 2
5 1

最大宽度 = 5，最大高度 = 5，答案 = $2 \times (5+5) = 20$，与输出一致。

第二个样例：

2 2
1 1
1 2

最大宽度 = 2，最大高度 = 2，答案 = $2 \times (2+2) = 8$，与输出一致。

标程代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int maxw = 0, maxh = 0;
        for (int i = 0; i < n; ++i) {
            int w, h;
            cin >> w >> h;
            maxw = max(maxw, w);
            maxh = max(maxh, h);
        }
        cout << 2 * (maxw + maxh) << "\n";
    }
    return 0;
}