[BZOJ 3170] [TJOI2013]松鼠聚会

Posted on | In , | Views:

题目链接

BZOJ 3170

做法

我们发现从点$i$走到点$j$所需要的最小步数为$Max(abs(x_i-x_j),abs(y_i-y_j))$
我们定义这个最小步数为点$i$与点$j$的切比雪夫距离。
我们常见的还有一个两点间的距离为曼哈顿距离，也就是$abs(x_i-x_j)+abs(y_i-y_j)$
我们发现当我们把原来一个点$(x,y)$改为$(x+y,x-y)$后，原坐标下的曼哈顿距离就变成了新坐标下的切比雪夫距离。
而如果把原来一个点$(x,y)$改为$(\frac{x+y}{2},\frac{x-y}{2})$,原坐标下的切比雪夫距离就变成了新坐标下的曼哈顿距离。
按照定义展开后不难证明。
那么原问题就变成了平面上$n$个点，找到其中一个点使得这个点到其他点的曼哈顿距离最小。
把所有点按照$x$坐标排序，在求出$y$坐标的排名，按照排名对$y$求个前缀和，就可以很方便的算出了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,x,y,t;
int id[N];
LL allx,ally,pre,now,ans=1e18;
LL sum[N];
struct node{
    int x,y;
}a[N];
struct sor{
    int x,id;
}q[N];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline bool cmp(node a,node b){
    return a.x<b.x;
}
inline bool cmp1(sor a,sor b){
    return a.x<b.x;
}
int main(){
    read(n);
    for (int i=1;i<=n;i++){
        read(x),read(y);
        a[i].x=x+y;
        allx+=a[i].x;
        a[i].y=x-y;
        ally+=a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++){
        q[i]=(sor){a[i].y,i};
    }
    sort(q+1,q+n+1,cmp1);
    for (int i=1;i<=n;i++){
        id[q[i].id]=i;
    }
    for (int i=1;i<=n;i++) sum[id[i]]=a[i].y;
    for (int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for (int i=1;i<=n;i++){
        pre+=a[i].x;
        now=allx-pre-1ll*(n-i)*a[i].x+1ll*i*a[i].x-pre;
        now+=1ll*(id[i]-1)*a[i].y-sum[id[i]-1]+ally-sum[id[i]-1]-1ll*(n-id[i]+1)*a[i].y;
        ans=min(ans,now);
    }
    printf("%lld",ans/2);
    return 0;
}