BZOJ_3210_花神的浇花集会_切比雪夫距离

2024-04-07 10:47:20

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)转化为曼哈顿距离求解。

如果是曼哈顿距离就可以把横纵坐标分开来求。

可以用数学方法证明排序后中位数最优。

但有可能答案(x,y)不能用原来坐标为整数的点表示。

出现这种情况需要用(x,y-1),(x,y+1),(x-1,y),(x+1,y)几个点带进去取个min。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 100050

typedef long long ll;

int xx[N],yy[N],n;

ll ans;

int fabs(int x){return x>0?x:-x;}

ll solve(int x,int y) {

    ll re=0;

    int i;

    for(i=1;i<=n;i++) re+=fabs(xx[i]-x)+fabs(yy[i]-y);

    return re>>1;

}

int main() {

    scanf("%d",&n);

    int i,x,y;

    for(i=1;i<=n;i++) {

        scanf("%d%d",&xx[i],&yy[i]);

        x=xx[i],y=yy[i];

        xx[i]=x-y;

        yy[i]=x+y;

    }

    sort(xx+1,xx+n+1);

    sort(yy+1,yy+n+1);

    x=xx[n+1>>1],y=yy[n+1>>1];

    if(x%2==y%2) printf("%lld\n",solve(x,y));

    else printf("%lld\n",min(solve(x-1,y),min(solve(x+1,y),min(solve(x,y-1),solve(x,y+1)))));

}