首页 > 分享 > BZOJ 3210 花神的浇花集会（切比雪夫曼哈顿）

BZOJ 3210 花神的浇花集会（切比雪夫曼哈顿）

花匠小妙招
2024-12-14 17:19

3210: 花神的浇花集会

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

Source

mjmjmj命题Stilwell制作数据

题目大意：
给定平面上的n个点，求一个点到这n个点的切比雪夫距离之和最小

思路：
有定理：对于点对(x,y)，变换成(x+y,x-y)，那么两两之间的切比雪夫距离=曼哈顿距离/2。
由于曼哈顿距离中横纵坐标不互相干扰，因此我们可以将横纵坐标分开处理。
每一维要选一个坐标，到其他所有坐标的绝对值之和最小，就是中位数。但是直接选择两个中位数得到的点，横纵坐标奇偶性可能不同，这样代回计算中就是整点。
因此如果得到的点横纵坐标奇偶性相同直接输出距离，不同的话选择周围的四个点进行判定，选择最小的ans输出即可。

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #define N 100010 #define LL long long using namespace std; int n; int x[N], y[N], a[N], b[N]; LL solve(int X, int Y){ LL rt = 0; for(int i=1; i<=n; i++) rt += abs(x[i] - X) + abs(y[i] - Y); return rt; } int main(){ scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d%d", &a[i], &b[i]); x[i] = a[i] + b[i]; y[i] = a[i] - b[i]; } sort(x+1, x+n+1); sort(y+1, y+n+1); int X = x[(n+1)/2], Y = y[(n+1)/2];//中位数 if( ((X ^ Y) & 1) == 0 )//奇偶性不同，转回原图时/2不为整点 printf("%lldn", solve(X, Y) / 2); else { LL ans1 = min(solve(X+1,Y), solve(X-1,Y)), ans2 = min(solve(X,Y+1), solve(X,Y-1)); printf("%lldn", min(ans1 / 2, ans2 / 2)); } return 0; }

123456789101112131415161718192021222324252627282930313233343536