题目分析

本题要求将 $n$ 个天然气井与 $n$ 个中转站进行一一匹配，每条管道从天然气井 $(x_i, y_i)$ 连接到中转站 $(x_j', y_j')$，管道的走向必须是：

• 从天然气井先向 $x$ 轴正方向（向右）
• 然后向 $y$ 轴负方向（向下）

最终目标是最小化所有管道的总长度。

关键观察

1. 管道路径分析

由于管道必须先向右后向下，从井 $(x, y)$ 到中转站 $(x', y')$ 的路径长度为：

$$(x' - x) + (y - y') = (x' - x) + (y - y')$$

2. 总长度计算

对于完美匹配，总长度为：

$$\sum_{i=1}^n (x_i' - x_i) + \sum_{i=1}^n (y_i - y_i') = \left(\sum_{i=1}^n x_i' - \sum_{i=1}^n x_i\right) + \left(\sum_{i=1}^n y_i - \sum_{i=1}^n y_i'\right) $$

重要发现：总长度实际上与具体的匹配方案无关！

算法思路

1. 总长度计算

直接使用公式：

$$\text{总长度} = \left(\sum \text{中转站}x - \sum \text{井}x\right) + \left(\sum \text{井}y - \sum \text{中转站}y\right) $$

2. 构造任意合法匹配

虽然总长度固定，但我们仍需要输出一种匹配方案。使用贪心+扫描线方法：

算法步骤：

1. 坐标变换：将 $y$ 坐标取反（$y = 10^6 - y$），便于统一处理
2. 排序处理：将所有点（井和中转站）按 $x$ 坐标从大到小排序
3. 扫描匹配：
   • 从右向左扫描
   • 遇到中转站：加入集合
   • 遇到井：从集合中选择 $y$ 坐标最小的中转站匹配

代码详解

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

struct node {
    int x, y, type, id;
    bool operator<(const node &rhs) const {
        if (x != rhs.x) return x < rhs.x;
        if (y != rhs.y) return y < rhs.y;
        if (type != rhs.type) return type < rhs.type;
        return id < rhs.id;
    }
};

struct point {
    int x, y, id;
    bool operator<(const point &rhs) const {
        if (y != rhs.y) return y < rhs.y;
        if (x != rhs.x) return x < rhs.x;
        return id < rhs.id;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int ans = 0, n;
    cin >> n;
    vector<node> vec;
    set<point> s;

    // 读取天然气井坐标并计算部分和
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        ans += x - y;                    // 累加 (x_i - y_i)
        y = 1e6 - y;                    // y坐标变换，便于处理
        vec.push_back({x, y, 0, i});    // type=0表示天然气井
    }

    // 读取中转站坐标并计算部分和
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        ans += y - x;                    // 累加 (y_i' - x_i')
        y = 1e6 - y;                    // y坐标变换
        vec.push_back({x, y, 1, i});    // type=1表示中转站
    }
    
    // 输出总长度：-ans = (∑x' - ∑x) + (∑y - ∑y')
    cout << 0 - ans << '\n';
    
    // 按x坐标从大到小排序
    sort(begin(vec), end(vec));
    reverse(begin(vec), end(vec));

    // 扫描线匹配
    for (auto [x, y, t, id] : vec) {
        if (!t) {  // 天然气井
            // 选择y坐标最小的中转站匹配
            auto it = s.lower_bound({x, y, 0});
            auto [a, b, d] = *it;
            s.erase(it);
            cout << id + 1 << ' ' << d + 1 << '\n';
        } else {   // 中转站
            s.insert({x, y, id});
        }
    }
}

正确性证明

1. 总长度不变性

无论匹配方案如何，总长度始终为：

$$(\sum x_i' - \sum x_i) + (\sum y_i - \sum y_i')$$

2. 匹配可行性

• 从右向左扫描确保井的 $x$ 坐标 ≤ 匹配中转站的 $x$ 坐标
• 选择 $y$ 坐标最小的中转站确保满足 $y$ 坐标约束
• 坐标变换 $y = 10^6 - y$ 将原问题的 $y$ 坐标比较反转

时间复杂度

• 排序：$O(n \log n)$
• 扫描匹配：$O(n \log n)$（set操作）
• 总复杂度：$O(n \log n)$，适用于 $n \le 50,000$

样例验证

输入：

3
3 5
1 2  
4 3
6 3
5 2
2 1

计算：

• $\sum x_i = 3+1+4 = 8$, $\sum y_i = 5+2+3 = 10$
• $\sum x_i' = 6+5+2 = 13$, $\sum y_i' = 3+2+1 = 6$
• 总长度 = $(13-8) + (10-6) = 5 + 4 = 9$

输出匹配方案满足所有约束条件。

总结

本题的关键在于发现总长度与匹配方案无关的数学性质，然后使用扫描线方法构造任意合法匹配。算法高效且易于实现。