【BZOJ3170】[Tjoi 2013]松鼠聚会

2015.08.12 08:51 Wed | 30次阅读 | 旧日oi | 固定链接 | 源码

Description

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

题解

两点之间的距离定义为max(abs(x-x0),abs(y-y0)),这是切比雪夫距离,它可以通过坐标变换变成曼哈顿距离
x=(x+y)/2,y=(x-y)/2。
然后先按y从小到大排序,处理处前缀和,然后按x排序。
对每一个点计算答案时,x方向的答案很明了,y方向的话二分查找出当前点的y的排名,然后用刚才记录的前缀和计算即可。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define N 100005
int n;
struct node
{
    double x,y;
}a[N];
bool cmp1(const node &a,const node &b)
{
    return a.y<b.y;
}
bool cmp2(const node &a,const node &b)
{
    return a.x<b.x;
}
double sumx[N],sumy[N],num[N];
int main()
{   
    cin>>n;
    for(int x,y,i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        a[i].x=(x+y)*1.0/2;a[i].y=(x-y)*1.0/2;
    }
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++)
    {
        num[i]=a[i].y;
        sumy[i]=sumy[i-1]+a[i].y;
    }
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=n;i++) sumx[i]=sumx[i-1]+a[i].x;
    double ans=23333333333333333.0,tmp;
    for(int i=1;i<=n;i++)
    {   
        tmp=a[i].x*(i-1)-sumx[i-1]+(sumx[n]-sumx[i])-a[i].x*(n-i);
        int t=lower_bound(num+1,num+n+1,a[i].y)-num;
        tmp+=a[i].y*(t-1)-sumy[t-1]+(sumy[n]-sumy[t])-a[i].y*(n-t);
        ans=min(ans,tmp);
    }   
    printf("%lld\n",(ll)ans);
}```