BZOJ3210 花神的浇花集会

2014.12.23 10:06 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Solution

显然,大体思路和上一道题BZOJ3170很像,将切比雪夫距离化为曼哈顿距离进行求解。显然,一道题如果适合,则它的每个坐标一定至少符合一个学生的爱好。于是,只需取中位数即可。由于在还原过程中有可能最优解不出现在整点上,所以需要对求得的坐标进行抖动,更新答案。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005

int n;
long long tx,ty,ansx,ansy,ans=1LL<<62;
const int   dx[10]={0,0,0,1,-1,1,1,-1,-1},
            dy[10]={0,1,-1,0,0,1,-1,1,-1};

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,a,b;
    O_o(){}
    O_o(int _p):p(_p){ x=read(),y=read(); a=x-y; b=x+y; }
    bool operator <(const O_o &p) const
    {
        return a<p.a;
    }
}q[N];

long long check(int x,int y)
{
    long long re=0;
    for(int i=1;i<=n;i++)
        re+=max(abs(q[i].x-x),abs(q[i].y-y));
    return re;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        q[i]=O_o(i);
    sort(q+1,q+n+1);
    tx=q[n/2+1].a;
    for(int i=1;i<=n;i++)
        swap(q[i].a,q[i].b);
    sort(q+1,q+n+1);
    ty=q[n/2+1].a;
    ansx=(tx+ty)/2, ansy=(ty-tx)/2;
    for(int i=1;i<=9;i++)
        ans=min(ans,check(ansx+dx[i],ansy+dy[i]));
    cout<<ans<<endl;
}