BZOJ3210: 花神的浇花集会

Description

在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。

具体浇水活动详情请见BZOJ3153

但这不是重点

花神出了好多题，每道题都有两个参考系数：代码难度和算法难度

花神为了准备浇花集会的题，必须找一道尽量适合所有人的题

现在花神知道每个人的代码能力x和算法能力y，一道题（代码难度X算法难度Y）对这个人的不适合度为 Max ( abs ( X – x ) , abs ( Y – y ) )

也就是说无论太难还是太简单都会导致题目不适合做（如果全按花神本人能力设题，绝对的全场爆0的节奏，太简单，则体现不出花神的实力）

当然不是每次都如花神所愿，不一定有一道题适合所有人，所以要使所有人的不合适度总和尽可能低

花神出了100001*100001道题，每道题的代码难度和算法难度都为0，1，2，3，……，100000

Input

第一行一个正整数N，表示花神有N个学生，花神要为这N个学生选一道题

接下来N行，每行两个空格隔开的整数x[i],y[i]，表示这个学生的代码能力和算法能力

Output

一个整数，表示最小的不合适度总和

Sample Input

3

1 2

2 1

3 3

Sample Output

HINT

对于100%的数据，n<=100000,0<=x[i],y[i]<=100000

将（x,y）转化成（x+y,x-y）可以将切比雪夫距离转化成曼哈顿距离(自己推一推)，A、B的切比雪夫距离就是A`、B`曼哈顿距离的一半。

那么可以将x、y分离处理，排序中位数即可。注意如果最后选的最优的X、Y代回去不是整数，要在其上下左右中选个最优方案。

还有就是这道题不知道怎么IO优化就是用不了。

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,BufferSize,stdin);
        tail=(head=buffer)+l;
    }
    return *head++;
}
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
const int maxn=100010;
int n,x[maxn],y[maxn];
ll solve(int X,int Y) {
    ll ans=0;
    rep(i,1,n) ans+=abs(X-x[i])+abs(Y-y[i]);
    return ans;
}
int main() {
    n=read();
    rep(i,1,n) {
        int a=read(),b=read();
        x[i]=a+b;y[i]=a-b;
    }
    sort(x+1,x+n+1);sort(y+1,y+n+1);
    int X=x[n+1>>1],Y=y[n+1>>1];
    if(~(X^Y)&1) printf("%lld
",solve(X,Y)/2);
    else printf("%lld
",min(min(solve(X-1,Y),solve(X,Y-1)),min(solve(X+1,Y),solve(X,Y+1)))/2);
    return 0;
}

View Code