关于求曼哈顿距离之和最大的原理

Question

给你n个点（n为偶数），找出n/2个点对，使这n/2个点对的曼哈顿距离之和最大，ac代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct nod{int x,y,i;}s[300001];
bool cmp1(nod a,nod b){return a.x<b.x;}
bool cmp2(nod a,nod b){return a.y<b.y;}
int main(){
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>s[i].x>>s[i].y,s[i].i=i;
        sort(s+1,s+1+n,cmp1);
        sort(s+1,s+1+n/2,cmp2);sort(s+n/2+1,s+n+1,cmp2);
        for(int i=1;i<=n/2;i++){
            cout<<s[i].i<<" "<<s[n-i+1].i<<"\n";
        }
    }
    return 0;
}

但是为什么呢，这么写的原理是什么

Answer 1

一杯年华@编程空间帮您解答，本答案结合 ChatGPT4.0和DeepSeek整理
我曾经遇到过类似的问题，当时也是在思考如何最大化多个点对的曼哈顿距离之和，摸索了很久才理清思路。

问题分析

我们的目标是从n个点（n为偶数）中选出n/2个点对，让这些点对的曼哈顿距离之和最大。这里的曼哈顿距离是指两个点(x₁,y₁)和(x₂,y₂)之间的|x₁-x₂| + |y₁-y₂|，这个距离可以拆分为x方向的差和y方向的差之和，所以总距离之和就是所有点对x方向差的总和加上y方向差的总和。

两种解决方案

1. 全组合暴力筛选法
   列出所有可能的点对组合（共n/2对，且每个点只参与一次），计算每一种组合的曼哈顿距离总和，然后选择最大的那个。但这种方法的问题很明显：当n较大时，组合数量会爆炸式增长，计算量极大，完全不具备实用性，只能用于n非常小的场景。

2. 拆分维度优化法
   利用曼哈顿距离可拆分为x和y两个独立维度的特性，分别最大化两个维度的距离贡献。具体来说：

   • 对于x方向，要让每对的|x₁-x₂|尽可能大。将所有点按x坐标排序后，前n/2个点作为一组，后n/2个点作为另一组，两组交叉配对（比如第1组的第i个点和第2组的第i个点配对），能让x方向的总距离最大。
   • 对于y方向，同样在分好的两组内，各自按y坐标排序，再交叉配对，确保y方向的总距离也最大。

最优方案详解

最优方案就是上述的“拆分维度优化法”，核心逻辑是：

• 曼哈顿距离的总和等于x方向距离总和与y方向距离总和的相加，因此可以分开优化两个维度。
• 对于x方向，将点按x排序后，前半组和后半组交叉配对（比如最小x与最大x、次小x与次大x等），能最大化每对的x差，从而让x方向的总距离最大。
• 对于y方向，在x方向分好的两组内，各自按y排序后再交叉配对，同样能最大化每对的y差，让y方向的总距离最大。

这种方法既保证了总距离最大，又高效可行，适用于各种规模的n。

希望我的分析能帮到你，楼主采纳。如有问题请继续留言。