[Tjoi 2013]松鼠聚会

3170: [Tjoi 2013]松鼠聚会

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1318 Solved: 664
[Submit][Status][Discuss]

Description

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

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

HINT

Source

　　暴力算法O（n²）,直接暴力枚举每一个点作为集合点，然后计算距离。

提供一种太暴力的做法运用贪心策略

　　我们发现应该尽量让松鼠少走路，那么集合点应该尽量靠近中间，计算时间复杂度发现差不多可以扫1000个点

那我们就可以避免扫10W而去扫（n/2-500,n/2+500）,不断更新答案，理论上可以被卡掉。。但是貌似还没被卡过？？

　　然后说正解：

　　　　题目要求的是Max（|x1-x2|,|y1-y2| ); 求得是切比雪夫距离

　　切比雪夫是啥？？不喜欢他（她？）。。我们还是换成曼哈顿吧

　　简单证明一下：

　　　　　　对于曼哈顿距离，d=(|x1-x2|+|y1-y2|);

　　我们把式子展开：

　　d=Max(Max(x1-x2,x2-x1)+Max(y1-y2,y2-y1))

　　d=Max(x1-x2+y1-y2,x1-x2+y2-y1,x2-x1+y1-y2,x2-x1+y2-y1)

　　将同一个坐标合并起来:发现：

　　d=Max( (x1+y1) - (x2+y2 ) , (x1-y1)-(x2-y2), -(x1-y1)+(x2-y2),-(x1+y1)+(x2+y2))

　　d=Max( | (x1+y1) -(x2+y2) |,| (x1-y1)-(x2-y2) | )

所以x=x1+y1,y=x1-y1 就转化成了切比雪夫距离，换一下元

x=（x+y）/2，y=(x-y)/2就是把切比雪夫转化为曼哈顿

我们在排一下序，求个前缀和就完事了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 struct sta{
 8     ll x,y;
 9 }k[100005];
10  
11 template <typename _t>
12 inline _t read(){
13     _t sum=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0',ch=getchar();}
16     return sum*f;
17 }
18  
19 int n;
20 int lx[100005],ly[100005];
21 ll sumx[100005],sumy[100005];
22 int main(){
23     n=read<int>();
24     for(int i=1;i<=n;++i){
25         int x,y;
26         x=read<int>(),y=read<int>();
27         k[i].x=lx[i]=x+y,k[i].y=ly[i]=x-y;
28     }
29     sort(lx+1,lx+n+1);sort(ly+1,ly+n+1);
30     for(int i=1;i<=n;++i)
31         sumx[i]=sumx[i-1]+lx[i],
32         sumy[i]=sumy[i-1]+ly[i];
33     ll ans=(ll)1e30;
34     for(int i=1;i<=n;++i){
35         int pos=lower_bound(lx+1,lx+n+1,k[i].x)-lx;
36         ll sum=sumx[n]-sumx[pos]-k[i].x*(n-pos)+k[i].x*pos-sumx[pos];
37         pos=lower_bound(ly+1,ly+n+1,k[i].y)-ly;
38         sum+=sumy[n]-sumy[pos]-k[i].y*(n-pos)+k[i].y*pos-sumy[pos];     
39         ans=min(ans,sum);
40     }
41     printf("%lld
",ans>>1);
42     return 0;
43 }