hdu_4311_Meeting point-1(曼哈顿距离）及其拓展

题目链接

题目描述

给定n个点，找出其中一个点，使得其他点到这个点的曼哈顿距离和最小，求这个最小距离和。

Sample Input

4
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
5
-5 1
-1 3
3 1
3 -1
1 -1
10
-1 -1
-3 2
-4 4
5 2
5 -4
3 -1
4 3
-1 -2
3 4
-2 2

Sample Output

26
20
20
56

解题思路

曼哈顿距离：两个点的横纵坐标的差的绝对值之和；
$$dic=|x_1-x_2|+|y_1-y_2|$$
题目要求计算的结果为
$$dic=\sum _{i=1}^n|x_i-x|+\sum _{i=1}^n|y_i-y|$$
暴力解法就是，遍历所有点，计算其到其他所有点的曼哈顿距离和，记录最小值，时间复杂度是O($n^2$)；
优化过程：预处理两个数组sum_x[n],sum_y[n];
sum_x[i]表示到序号i为止的点的横坐标的和。
sum_y[i]表示到序号i为止的点的纵坐标的和。
将所有点按x排序后:
$su{m}_x={\sum }_{i=1}^n|x_i-x|=(i-1)\ast x[i]-su{m}_x[i-1]+su{m}_x[n]-su{m}_x[i]-(n-i)\ast x[i];$
将所有点按y排序后:
$su{m}_y={\sum }_{i=1}^n|y_i-y|=(i-1)\ast y[i]-su{m}_y[i-1]+su{m}_y[n]-su{m}_y[i]-(n-i)\ast y[i];$
时间复杂度为O(nlog(n));

AC代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn=100005;
struct note
{int x,y,id;
} a[maxn];
int x[maxn],y[maxn],n;
LL numx[maxn],numy[maxn];bool cmp1(note a,note b)
{return a.x<b.x;
}bool cmp2(note a,note b)
{return a.y<b.y;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);LL sumx=0,sumy=0;for(int i=1; i<=n; i++){scanf("%d%d",&x[i],&y[i]);a[i].x=x[i];a[i].y=y[i];a[i].id=i;sumx+=x[i];sumy+=y[i];}sort(a+1,a+n+1,cmp1);LL ans=0;for(int i=1; i<=n; i++){ans+=a[i].x;int j=a[i].id;numx[j]=(LL)x[j]*(2*i-n)+sumx-2*ans;}sort(a+1,a+1+n,cmp2);ans=0;for(int i=1; i<=n; i++){ans+=a[i].y;int j=a[i].id;numy[j]=(LL)y[j]*(2*i-n)+sumy-2*ans;}ans=numy[1]+numx[1];for(int k=2; k<=n; k++)ans=min(ans,numx[k]+numy[k]);printf("%I64d\n",ans);}return 0;
}

####扩展
给定n个点的坐标，求出一个点（不一定是n个点之一），使得其到其他所有点的曼哈顿距离和最小；
易知，要求的点的x值必定是n个点中某一个点的x值，y值必定是n个点中某一个点的y值，但未必是同一个点的x值和y值；求x和y的过程跟上面一题一样。