bzoj3170[Tjoi 2013]松鼠聚会

有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

Sample Output

20

题解：

对于这题，我们可以得到d(i,j)=max(|xi-xj|,|yi-yj|)，

设x’=(x+y)/2,y’=(x-y)/2

那么d(i,j)=|xi’-xj’|+|yi’-yj’|

x，y轴可以分开统计

先是统计x轴，将所有松鼠的x’排序

用前缀和和后缀和求出某个松鼠到其他松鼠的X轴距离

Xi*(i-1)-sum(1..i-1)+sum(i+1..n)-(n-i)*Xi

y轴同理

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define N 100007
 5 #define ll long long
 6 using namespace std;
 7 
 8 int n;
 9 double ans=1e20;
10 ll sx,sy,ax[N],bx[N],ay[N],by[N];
11 struct point
12 {
13     ll x,y;
14     int num;
15 }a[N];
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 int main()
20 {
21     scanf("%d",&n);
22     for(int i=1;i<=n;i++)
23     {
24        ll x,y;
25        scanf("%lld%lld",&x,&y);
26        a[i].x=x+y;a[i].y=x-y;
27     }
28     sort(a+1,a+n+1,cmpy);
29     for(int i=1;i<=n;i++)
30     {
31         ay[i]=ay[i-1]+a[i].y;
32         by[n-i+1]=by[n-i+2]-a[n-i+1].y;
33         a[i].num=i;
34     }
35     sort(a+1,a+n+1,cmpx);
36     for(int i=1;i<=n;i++)
37     {
38         ax[i]=ax[i-1]+a[i].x;
39         bx[n-i+1]=bx[n-i+2]-a[n-i+1].x;
40     }
41     for(int i=1;i<=n;i++)
42     {
43         ll tmp=0;
44         tmp+=ax[n]-ax[i]-(n-i)*(ax[i]-ax[i-1]);
45         tmp+=bx[1]-bx[i]-(i-1)*(bx[i]-bx[i+1]);
46         int j=a[i].num;
47         tmp+=ay[n]-ay[j]-(n-j)*(ay[j]-ay[j-1]);
48         tmp+=by[1]-by[j]-(j-1)*(by[j]-by[j+1]);
49         if(tmp<ans)ans=tmp;
50     }
51     printf("%.0lf",ans/2);
52 }