Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1804  Solved: 968
[Submit][Status][Discuss]

Description

有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input

第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5
下面N行，每行给出x,y表示其家的坐标。
-10^9<=x,y<=10^9

Output

表示为了聚会走的路程和最小为多少。

Sample Input

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

Sample Output

20   非常经典的高中数学证明题 首先要知道两个公式： max{a,b}=(|a+b|+|a-b|)/2 ||a|+|b||+||a|-|b||=|a+b|+|a-b| \[ans=\sum ^{n}_{j=1} |(x_{i}+y_{i})-(x_{j}+y_{j})|+|(x_{i}-y_{i})-(x_{j}-y_{j})|\] 绝对值可以用排序满足条件 设X=xi+yi，Y=xi-yi 对X进行排序，再计算X前缀和f[i] 上述|(xi+yi)-(xj+yj)|=(i-1)*Xi-f[i-1]+f[n]-f[i]-(n-i)*Xi=i*Xi-f[i]+f[n]-f[i]-(n-i)*Xi Y同理，|(xi-yi)-(xj-yj)|=(i-1)*Yi-f[i-1]+f[n]-f[i]-(n-i)*Yi=i*Yi-f[i]+f[n]-f[i]-(n-i)*Yi 最后统计两者之和，取最小值就是答案 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;  5 #define LL long long
 6 
 7 const LL INF=0x7f7f7f7f7f7f7f7f;  8 const int MAXN=100005;  9 struct Point 10 { 11  LL x,y,ans; 12 }P[MAXN]; 13 
14 LL n,ans=INF; 15 LL f[MAXN]; 16 
17 bool cmpx(Point A,Point B){return A.x<B.x;} 18 bool cmpy(Point A,Point B){return A.y<B.y;} 19 
20 int main() 21 { 22     scanf("%d",&n); 23     for(int i=1;i<=n;i++) 24  { 25         int x,y; 26         scanf("%d%d",&x,&y); 27         P[i].x=x+y; 28         P[i].y=x-y; 29  } 30     sort(P+1,P+n+1,cmpx); 31     for(int i=1;i<=n;i++) f[i]=f[i-1]+P[i].x; 32     for(int i=1;i<=n;i++) 33         P[i].ans+=i*P[i].x-f[i]+f[n]-f[i]-(n-i)*P[i].x; 34     sort(P+1,P+n+1,cmpy); 35     for(int i=1;i<=n;i++) f[i]=f[i-1]+P[i].y; 36     for(int i=1;i<=n;i++) 37  { 38         P[i].ans+=i*P[i].y-f[i]+f[n]-f[i]-(n-i)*P[i].y; 39         if(P[i].ans<ans) ans=P[i].ans; 40  } 41     cout<<(ans>>1); 42     return 0; 43 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄