题目描述

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

具体浇水活动详情请见BZOJ3153

但这不是重点

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

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

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

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

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

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

输入

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

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

输出

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

样例输入

3

1 2

2 1

3 3

样例输出

3

---

题解

数论

题目所求的是切比雪夫距离，我们可以将点$(x,y)$旋转为点$(x+y,x-y)$，这样原图中的切比雪夫距离就变为了新图中的曼哈顿距离。

然后横纵坐标分开处理，即求使$|x-p_1|+|x-p_2|+...+|x-p_n|$最小的x，由数论知识可知$x$为$p_1,p_2,...,p_n$的中位数。

最后得到一个新图中的点$(x,y)$，如果这个点合法即为答案，如果不合法（即没有原图中合法的点旋转后得到它，即x与y的奇偶性不同），则需要尝试其相邻的4个点，取距离最小值即为答案。

#include 
     
      #include 
      
       #include 
       
        #define N 100010using namespace std;typedef long long ll;int n , px[N] , py[N];ll solve(int x , int y){	int i;	ll ans = 0;	for(i = 1 ; i <= n ; i ++ ) ans += abs(px[i] - x) + abs(py[i] - y);	return ans >> 1;}int main(){	int i , x , y;	scanf("%d" , &n);	for(i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &x , &y) , px[i] = x + y , py[i] = x - y;	sort(px + 1 , px + n + 1) , sort(py + 1 , py + n + 1);	x = px[(n + 1) >> 1] , y = py[(n + 1) >> 1];	if((x ^ y) & 1) printf("%lld\n" , min(min(solve(x - 1 , y) , solve(x , y - 1)) , min(solve(x + 1 , y) , solve(x , y + 1))));	else printf("%lld\n" , solve(x , y));	return 0;}