Symmetrical Painting - 题解

标签与难度

标签: 计算几何, 扫描线, 差分思想, 函数图像, 坐标变换, 凹函数难度: 1900

题目大意喵~

各位Master，大家好呀~ ฅ'ω'ฅ

这道题目是这样的：我们有一个无限大的白色坐标平面。然后，我们在上面画了 $N$ 个黑色的长方形。第 $i$ 个长方形的左下角坐标是 $(i-1, L_i)$ ，右上角坐标是 $(i, R_i)$ 。也就是说，每个长方形的宽度都是1，它们在x轴上紧挨着排列。

现在，我们想让最终的黑色图案关于某条水平直线 $y = y_0$ 对称。为了达到这个目的，我们可以把一些本来是黑色的区域重新涂成白色。我们的目标是，在满足对称性的前提下，让剩下的黑色区域面积最大。请问这个最大面积是多少呢？喵~

解题思路分析

这道题看起来有点几何的感觉，但别怕，让我带你一步步把它分解开来，其实很有趣的哦！

1. 对称意味着什么？

首先，我们要理解“关于直线 $y=y_0$ 对称”是什么意思。如果一个点 $(x, y)$ 是黑色的，那么它关于 $y=y_0$ 的对称点 $(x, 2y_0 - y)$ 也必须是黑色的。

但是，我们只能把黑色涂成白色，不能把白色涂成黑色。所以，如果一个点 $(x, y)$ 原本是黑色的，但它的对称点 $(x, 2y_0 - y)$ 原本是白色的，那为了保持对称性，我们只好委屈一下，把 $(x, y)$ 也涂成白色了，呜~

这意味着，对于一条固定的对称轴 $y=y_0$ ，最终留下的黑色区域，其实是原始黑色区域和它关于 $y=y_0$ 翻折后的图形的交集！我们的任务，就是找到一个最好的 $y_0$ ，使得这个交集的面积最大。

2. 单个长方形的贡献

我们有 $N$ 个长方形，它们在 x 轴上互不重叠。所以我们可以分别考虑每个长方形对总面积的贡献，然后把它们加起来。

考虑第 $i$ 个长方形，它占据的区域是 $x \in [i-1, i], y \in [L_i, R_i]$ 。它的宽度是1，所以它的面积就是它的高度 $R_i - L_i$ 。

当我们选择了一条对称轴 $y=y_0$ 时，这个长方形在 $y$ 轴上的范围 $[L_i, R_i]$ ，它关于 $y_0$ 的对称区间就变成了 $[2y_0 - R_i, 2y_0 - L_i]$ 。

为了保持对称，在 $x \in [i-1, i]$ 这个垂直条带上，留下的黑色部分的高度就是这两个区间的交集长度。两个区间 $[a, b]$ 和 $[c, d]$ 的交集长度是 $\max(0, \min(b, d) - \max(a, c))$ 。

所以，对于第 $i$ 个长方形，在对称轴为 $y_0$ 时，它贡献的面积是：

A_i(y_0) = \max(0, \min(R_i, 2y_0 - L_i) - \max(L_i, 2y_0 - R_i))

总面积就是所有长方形贡献之和：

A(y_0) = \sum_{i=1}^{N} A_i(y_0)

我们的目标就是找到 $\max_{y_0} A(y_0)$ 。

3. 函数的“形状”与坐标变换

这个 $A(y_0)$ 函数看起来好复杂呀，喵~ 让我们来画画看 $A_i(y_0)$ 的图像是什么样的。

随着 $y_0$ 从小到大变化：

当 $y_0$ 很小，对称区间 $[2y_0 - R_i, 2y_0 - L_i]$ 在 $[L_i, R_i]$ 的下方，没有交集，面积为0。
当 $y_0$ 增大到 $L_i$ 时，对称区间的上边界 $2y_0 - L_i$ 碰到了原区间的下边界 $L_i$ 。
当 $y_0$ 从 $L_i$ 增大到 $(L_i+R_i)/2$ 时，交集长度从0线性增加到 $R_i-L_i$ 。函数图像是一条斜率为 $+2$ 的直线。
当 $y_0 = (L_i+R_i)/2$ 时，两个区间完全重合，交集最大，就是原长方形的高度 $R_i-L_i$ 。
当 $y_0$ 从 $(L_i+R_i)/2$ 增大到 $R_i$ 时，交集长度从最大值线性减小到0。函数图像是一条斜率为 $-2$ 的直线。
当 $y_0$ 超过 $R_i$ 后，交集又变成0了。

所以， $A_i(y_0)$ 的函数图像是一个“帐篷”形状（或者叫三角形），在 $y_0 = (L_i+R_i)/2$ 处取得最大值。总面积函数 $A(y_0)$ 是 $N$ 个这样“帐篷”形状函数的叠加，它本身也是一个分段线性凹函数。

对于这种函数，它的最大值一定出现在它的“拐点”上。这些拐点就是每个小帐篷的拐点，即 $y_0 = L_i, y_0 = R_i, y_0 = (L_i+R_i)/2$ 这些地方。

但是， $(L_i+R_i)/2$ 可能是小数，处理起来好麻烦哦！这里有一个超级棒的技巧，喵~ 我们可以进行坐标变换！

令 $Y = 2y_0$ 。这样 $y_0 = Y/2$ 。我们把所有东西都用 $Y$ 来表示。

对称轴是 $Y/2$ 。
对称区间是 $[Y - R_i, Y - L_i]$ 。
原区间是 $[L_i, R_i]$ 。为了避免小数，我们把这两个区间都乘以2，变成 $[2L_i, 2R_i]$ 和 $[2Y - 2R_i, 2Y - 2L_i]$ 。这样比较起来太复杂了。

让我们换一种方式推导 $A_i$ 关于 $Y$ 的函数。 $A_i(Y/2) = \max(0, (R_i-L_i) - |(L_i+R_i) - Y|)$ 。这是一个以 $Y=L_i+R_i$ 为对称轴，高度为 $R_i-L_i$ 的帐篷！它的拐点变成了整数：

帐篷的左边角点在 $Y = (L_i+R_i) - (R_i-L_i) = 2L_i$ 。
帐篷的顶点在 $Y = L_i+R_i$ 。
帐篷的右边角点在 $Y = (L_i+R_i) + (R_i-L_i) = 2R_i$ 。

现在所有关键点 $2L_i, L_i+R_i, 2R_i$ 都是整数了，太棒啦！

4. 扫描线大法！

我们要求总面积函数 $G(Y) = \sum_{i=1}^{N} A_i(Y/2)$ 的最大值。 $G(Y)$ 是一个分段线性凹函数，它的导数（也就是斜率）只在这些关键点 $2L_i, L_i+R_i, 2R_i$ 处发生变化。

这启发我们使用扫描线算法！我们可以把 $Y$ 看作一条从左到右扫描的直线，把所有关键点看作“事件点”。

我们来分析一下 $G(Y)$ 的斜率（导数）在每个事件点如何变化：

对于单个帐篷函数 $A_i(Y/2)$ ，它的斜率在 $Y \in (2L_i, L_i+R_i)$ 区间是 $+1/2$ （因为面积是 $\frac{1}{2}(Y-2L_i)$ ... 等等，我好像把面积和高度搞混了）。

让我们重新审视一下 $A_i(y_0)$ 的斜率。

在 $y_0 \in (L_i, (L_i+R_i)/2)$ ，面积是 $2y_0 - 2L_i$ ，斜率是 $+2$ 。
在 $y_0 \in ((L_i+R_i)/2, R_i)$ ，面积是 $2R_i - 2y_0$ ，斜率是 $-2$ 。总面积函数 $A(y_0)$ 的斜率在 $y_0=L_i$ 处增加2，在 $y_0=(L_i+R_i)/2$ 处减少4，在 $y_0=R_i$ 处增加2。

为了避免浮点数，我们还是用 $Y=2y_0$ 。令 $g_i(Y) = A_i(Y/2)$ 。

当 $Y \in (2L_i, L_i+R_i)$ ， $g_i(Y) = Y - 2L_i$ ，斜率是 $+1$ 。
当 $Y \in (L_i+R_i, 2R_i)$ ， $g_i(Y) = 2R_i - Y$ ，斜率是 $-1$ 。

所以，总面积函数 $G(Y) = \sum g_i(Y)$ 的斜率变化如下：

在事件点 $Y=2L_i$ 处，斜率增加 1。
在事件点 $Y=L_i+R_i$ 处，斜率从+1变为-1，总变化是 $-2$ 。
在事件点 $Y=2R_i$ 处，斜率从-1变为0，总变化是 $+1$ 。

我们的扫描线算法就清晰了：

对每个长方形 $(L_i, R_i)$ $(L_{i}, R_{i})$ ，生成三个事件：(坐标, 斜率变化量)
- (2*L_i, +1)
- (L_i + R_i, -2)
- (2*R_i, +1)
将所有 $3N$ 个事件按坐标从小到大排序。
我们从左到右处理这些事件。维护 current_Y（当前扫描线位置），current_area（当前位置的总面积），和 slope（当前区间的斜率）。
从第一个事件点开始，current_area 初始化为0。
遍历事件点，从 current_Y 移动到下一个事件点 next_Y 时，面积的增量是 slope * (next_Y - current_Y)。我们更新 current_area，并用它来更新全局的最大面积 max_area。
到达 next_Y 后，处理掉所有在这个坐标的事件，更新 slope。
重复此过程直到所有事件处理完毕。

这样，我们就能在 $O(N \log N)$ 的时间里找到最大的面积啦！是不是很巧妙呢，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码~ 希望能帮到Master！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

// 定义事件结构体，喵~
// pos: 事件发生的坐标 (Y = 2 * y_0)
// delta_slope: 在这个坐标，总面积函数 G(Y) 的斜率变化量
struct Event {
    long long pos;
    int delta_slope;

    // 为了排序，我们需要一个比较函数
    bool operator<(const Event& other) const {
        if (pos != other.pos) {
            return pos < other.pos;
        }
        // 如果坐标相同，顺序不影响最终结果
        return delta_slope < other.delta_slope;
    }
};

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<Event> events;
    events.reserve(n * 3); // 预留空间，避免动态扩容

    for (int i = 0; i < n; ++i) {
        long long l, r;
        std::cin >> l >> r;

        // 对于每个长方形，生成三个关键事件点
        // 1. 在 Y = 2*L 处，斜率 +1
        events.push_back({2 * l, 1});
        // 2. 在 Y = L+R 处，斜率 -2
        events.push_back({l + r, -2});
        // 3. 在 Y = 2*R 处，斜率 +1
        events.push_back({2 * r, 1});
    }

    // 将所有事件按坐标排序
    std::sort(events.begin(), events.end());

    long long max_area = 0;
    long long current_area = 0;
    long long current_slope = 0;
    long long current_pos = events[0].pos;

    // 开始扫描线~
    for (size_t i = 0; i < events.size(); ) {
        long long next_pos = events[i].pos;

        // 从 current_pos 移动到 next_pos
        // 面积变化量 = 斜率 * 距离
        current_area += current_slope * (next_pos - current_pos);

        // 更新当前位置和最大面积
        current_pos = next_pos;
        max_area = std::max(max_area, current_area);

        // 处理所有在 next_pos 的事件，更新斜率
        size_t j = i;
        while (j < events.size() && events[j].pos == current_pos) {
            current_slope += events[j].delta_slope;
            j++;
        }
        // 跳到下一个不同的坐标
        i = j;
    }

    std::cout << max_area << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$ 我们为 $N$ 个长方形创建了 $3N$ 个事件。对这些事件进行排序是主要的时间开销，所以是 $O(3N \log(3N)) = O(N \log N)$ 。之后遍历一遍事件是线性的 $O(N)$ 。所以总的时间复杂度由排序决定，是 $O(N \log N)$ ，非常高效呢！
空间复杂度: $O(N)$ 我们需要一个数组或向量来存储 $3N$ 个事件，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题真是一次愉快的思维探险，喵~ 我们用到的知识点有：

问题转化: 把一个几何对称问题，转化成了求一个函数最大值的问题。这是解决算法题非常重要的一步！
函数图像分析: 通过分析单个元素贡献的函数 $A_i(y_0)$ 的形状（帐篷形），我们推断出总函数 $A(y_0)$ 是一个分段线性凹函数，其最大值必然在“拐点”处取得。
坐标变换: 使用 $Y=2y_0$ 的变换，巧妙地将可能出现浮点数的关键点全部转化为了整数，避免了精度问题，让计算变得简洁可靠。
扫描线与差分思想: 扫描线是处理一维（或多维）几何问题的强大工具。我们把函数斜率的变化看作在关键点发生的“事件”，通过累加这些变化（差分思想），我们就能高效地追踪函数值的变化，从而找到最大值。

希望这篇题解能对Master有所帮助！如果还有不明白的地方，随时可以再来问我哦~ 喵~ (ฅ^•ﻌ•^ฅ)

Symmetrical Painting - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 对称意味着什么？ ​

2. 单个长方形的贡献 ​

3. 函数的“形状”与坐标变换 ​

4. 扫描线大法！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​