壊すとword│E-olv

menu icon

BZOJ3170 [TJOI 2013]松鼠聚会

2014.12.23 08:31 Tue| 1 visits oi_2015| 2015_刷题日常| Text

庆祝不知道什么时候已经刷题200+了……

Solution

首先，两个松鼠的家(x,y)、(x',y')之间的距离为max(|x-x'|,|y-y'|)。展开并变形，得到max(|(x+y)-(x'+y')|,|(x-y)-(x'-y')|)。令X=(x+y)/2,Y=(x-y)/2，则上式可化简为|X-X'|+|Y-Y'|，即曼哈顿距离形式。这样我们可以用 $\mathcal O(n)$ 的时间分别处理出每一个点的横、纵坐标与其他点之间横、纵坐标的距离之和。这样便可得到答案。

以上的变形如果有异议的话可以从曼哈顿距离的形式往回推。

另外，学习到曼哈顿距离的英文还可以叫做Taxicab_Geometry。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n;
long long sum1[N],sum2[N],ans=1LL<<62;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct O_o
{
    long long p,x,y,dist;
    O_o(){}
    O_o(int _p):p(_p){ int a=read(),b=read(); x=a-b; y=a+b; }
    bool operator <(const O_o &a) const
    {
        return x<a.x;
    }
}q[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        q[i]=O_o(i);
    sort(q+1,q+n+1);
    for(int i=2;i<=n;i++)
        sum1[i]=sum1[i-1]+(i-1)*(q[i].x-q[i-1].x);
    for(int i=n-1;i;i--)
        sum2[i]=sum2[i+1]+(n-i)*(q[i+1].x-q[i].x);
    for(int i=1;i<=n;i++)
        q[i].dist=sum1[i]+sum2[i], swap(q[i].x,q[i].y);
    sort(q+1,q+n+1);
    for(int i=2;i<=n;i++)
        sum1[i]=sum1[i-1]+(i-1)*(q[i].x-q[i-1].x);
    for(int i=n-1;i;i--)
        sum2[i]=sum2[i+1]+(n-i)*(q[i+1].x-q[i].x);
    for(int i=1;i<=n;i++)
        q[i].dist+=sum1[i]+sum2[i];
    for(int i=1;i<=n;i++)
        ans=min(ans,q[i].dist);
    cout<<ans/2<<endl;
}
Newer