CF-1038-C. Manhattan Pairs（选择不重复的对，使得这个曼哈顿距离之和最大） · znzryb

## 思路讲解

那么容易想到，按照x排序，可以让sumx最大的方式就是排序，然后左边匹配右边。

而且，这样子匹配，左边的谁匹配右边的谁也是不重要的，至少对于sumx不重要，因此我们就可以按照使sumy最大的方式进行匹配。

同理，计算按照y排列能得到的答案即可。

## AC代码

[https://codeforces.com/contest/2122/submission/329811774](https://codeforces.com/contest/2122/submission/329811774)



::: 源代码

```cpp
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 定义点结构，包含x坐标、y坐标和索引
struct Point {
    ll x, y;
    int id;
};

// 主函数，用于处理每个测试用例
inline void processTestCase() {
    int n;
    cin >> n;  // 读取点的数量n（偶数）

    vector<Point> points(n);  // 创建存储点的向量
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;  // 读取每个点的坐标
        points[i].id = i + 1;  // 索引从1开始
    }

    // 定义按x坐标升序排序的lambda函数，如果x相同则按id升序
    auto compareByX = [](const Point& a, const Point& b) {
        return a.x < b.x || (a.x == b.x && a.id < b.id);
    };

    // 定义按y坐标升序排序的lambda函数，如果y相同则按id升序
    auto compareByY = [](const Point& a, const Point& b) {
        return a.y < b.y || (a.y == b.y && a.id < b.id);
    };

    // 定义按y坐标降序排序的lambda函数，如果y相同则按id升序
    auto compareByYDesc = [](const Point& a, const Point& b) {
        return a.y > b.y || (a.y == b.y && a.id < b.id);
    };

    // 定义按x坐标降序排序的lambda函数，如果x相同则按id升序
    auto compareByXDesc = [](const Point& a, const Point& b) {
        return a.x > b.x || (a.x == b.x && a.id < b.id);
    };

    vector<pair<int, int>> pairsOption1, pairsOption2;  // 存储两种方案的配对
    ll sumOption1 = 0, sumOption2 = 0;  // 存储两种方案的总曼哈顿距离

    // 方案1: 按x坐标分割成左右两组
    vector<Point> pointsSortedByX = points;  // 复制点集
    sort(pointsSortedByX.begin(), pointsSortedByX.end(), compareByX);  // 按x升序排序

    vector<Point> leftGroup(pointsSortedByX.begin(), pointsSortedByX.begin() + n / 2);  // 左半部分（小x）
    vector<Point> rightGroup(pointsSortedByX.begin() + n / 2, pointsSortedByX.end());  // 右半部分（大x）

    sort(leftGroup.begin(), leftGroup.end(), compareByY);  // 左组按y升序排序
    sort(rightGroup.begin(), rightGroup.end(), compareByYDesc);  // 右组按y降序排序

    for (int i = 0; i < n / 2; ++i) {
        ll dx = abs(leftGroup[i].x - rightGroup[i].x);  // 计算x差的绝对值
        ll dy = abs(leftGroup[i].y - rightGroup[i].y);  // 计算y差的绝对值
        sumOption1 += dx + dy;  // 累加到总和
        int a = leftGroup[i].id, b = rightGroup[i].id;  // 获取索引
        if (a > b) swap(a, b);  // 确保a < b
        pairsOption1.push_back({a, b});  // 添加配对
    }

    // 方案2: 按y坐标分割成上下两组
    vector<Point> pointsSortedByY = points;  // 复制点集
    sort(pointsSortedByY.begin(), pointsSortedByY.end(), compareByY);  // 按y升序排序

    vector<Point> bottomGroup(pointsSortedByY.begin(), pointsSortedByY.begin() + n / 2);  // 下半部分（小y）
    vector<Point> topGroup(pointsSortedByY.begin() + n / 2, pointsSortedByY.end());  // 上半部分（大y）

    sort(bottomGroup.begin(), bottomGroup.end(), compareByX);  // 下组按x升序排序
    sort(topGroup.begin(), topGroup.end(), compareByXDesc);  // 上组按x降序排序

    for (int i = 0; i < n / 2; ++i) {
        ll dx = abs(bottomGroup[i].x - topGroup[i].x);  // 计算x差的绝对值
        ll dy = abs(bottomGroup[i].y - topGroup[i].y);  // 计算y差的绝对值
        sumOption2 += dx + dy;  // 累加到总和
        int a = bottomGroup[i].id, b = topGroup[i].id;  // 获取索引
        if (a > b) swap(a, b);  // 确保a < b
        pairsOption2.push_back({a, b});  // 添加配对
    }

    // 选择总和更大的方案并输出配对
    if (sumOption1 >= sumOption2) {
        for (auto& pr : pairsOption1) {
            cout << pr.first << ' ' << pr.second << '\n';
        }
    } else {
        for (auto& pr : pairsOption2) {
            cout << pr.first << ' ' << pr.second << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int testCases;
    cin >> testCases;  // 读取测试用例数量
    while (testCases--) {
        processTestCase();  // 处理每个测试用例
    }
    return 0;
}
```


:::


## 心路历程（WA，TLE，MLE……）