问题分析

我们有 $n$ 个石头，每个石头有两个可能的坐标：$(x_i, y_i)$ 或 $(y_i, x_i)$。我们需要：

1. 为每个石头选择一个坐标（可能翻转或不翻转）
2. 用最小的矩形围栏包围所有石头
3. 在围栏长度最小的前提下，最小化翻转石头的总重量

关键观察

1. 围栏长度的计算

对于矩形 $[l, r] \times [d, u]$，围栏长度为：

2. 最优解的性质

由于每个石头有两个选择，所有可能的坐标都在直线 $y = x$ 对称。最优的包围矩形有以下四种情况：

1. 情况1：所有石头都不翻转，使用原始坐标
2. 情况2：所有石头都翻转，交换 $x$ 和 $y$
3. 情况3：一部分在原始位置，一部分翻转
4. 情况4：另一部分组合

但实际上，最优解对应的矩形边界由某些关键点决定。

算法思路

核心思想：枚举关键矩形

1. 预处理：对于每个石头 $(x_i, y_i)$，考虑其"规范形式" $(x', y')$，其中 $x' \ge y'$
2. 确定候选矩形：计算所有石头规范形式的包围矩形
3. 枚举四种可能的解：尝试不同的坐标分配方案
4. 选择最优：比较围栏长度和翻转代价

算法步骤

步骤1：预处理规范坐标

l = d = 11e8;  // 初始化为极大值
r = u = -11e8; // 初始化为极小值

for (int i = 0; i < n; ++i) {
    int x_ = x[i], y_ = y[i];
    // 规范形式：确保 x_ >= y_
    if (y_ > x_) 
        x_ = y[i], y_ = x[i];
    
    // 更新包围矩形边界
    if (l > x_) l = x_;
    if (r < x_) r = x_;
    if (u < y_) u = y_;
    if (d > y_) d = y_;
}

得到规范形式的包围矩形 $[l, r] \times [d, u]$。

步骤2：枚举四种情况

f(l, r, d, u);  // 情况1：使用原始坐标
f(d, u, l, r);  // 情况2：全部翻转
f(l, u, d, r);  // 情况3：混合1
f(d, r, l, u);  // 情况4：混合2

步骤3：评估函数 f

void f(long long l, long long r, long long d, long long u) {
    long long use = 0;
    
    for (int i = 0; i < n; ++i)
        if (x[i] < l || x[i] > r || y[i] < d || y[i] > u) {
            // 原始坐标不在矩形内，尝试翻转
            if (y[i] >= l && y[i] <= r && x[i] >= d && x[i] <= u)
                ss[i] = '1', use += m[i];  // 翻转可行
            else
                return;  // 翻转也不行，此方案不可行
        } else
            ss[i] = '0';  // 原始坐标就在矩形内
    
    // 更新最优解
    if ((u - d) + (r - l) < ans || 
        (u - d + r - l == ans && cost > use))
        ans = u - d + r - l, cost = use, memcpy(tt, ss, sizeof ss);
}

四种情况的几何意义

1. f(l, r, d, u)：使用原始坐标的规范包围矩形
2. f(d, u, l, r)：全部翻转后的包围矩形
3. f(l, u, d, r)：$x$ 边界用规范矩形的 $x$ 范围，$y$ 边界用规范矩形的 $y$ 范围
4. f(d, r, l, u)：$x$ 边界用规范矩形的 $y$ 范围，$y$ 边界用规范矩形的 $x$ 范围

复杂度分析

• 时间复杂度：$O(n)$
  • 预处理：$O(n)$
  • 四种枚举：每种 $O(n)$
• 空间复杂度：$O(n)$

样例验证

输入：

5
2 3 400
1 4 100  
2 2 655
3 4 100
5 3 277

处理过程：

1. 计算规范坐标和包围矩形
2. 枚举四种情况，找到最优解
3. 输出：围栏长度 $10$，翻转代价 $200$，方案 01010

算法正确性

为什么只需要枚举四种情况？

由于每个石头只有两种选择，且最优解对应的矩形边界由某些关键坐标决定。这四种情况覆盖了所有可能的边界组合。

为什么能保证最优？

• 枚举了所有可能的边界组合
• 对每种边界，贪心地选择翻转方案（只在必要时翻转）
• 比较所有可行解，选择最优

总结

本题的关键在于发现最优解对应的矩形边界只有有限的几种可能，通过预处理规范坐标和枚举关键情况，可以在线性时间内解决问题。这种"枚举关键情况 + 贪心选择"的思路在解决组合优化问题时非常有效。