51nod 3143 整装待发

51nod 3143 整装待发

题目链接
查了半天没有题解，于是乎这个题卡了我巨久，所以特意写个解析留给后来人！
首先：求max(|A-ai|,|B-bi|)，就是求切比雪夫距离，可以转化为曼哈顿距离进行计算，转化为曼哈顿距离，然后求出中位数，进行计算即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=1e5+10;
double a[N],b[N],c[N],d[N];
int k[N],q[N];
int main()
{int n;cin>>n;for(int i=0; i<n; i++){double x,y;scanf("%lf%lf",&x,&y);k[i]=x;q[i]=y;a[i]=(x+y)/2;//排序求中位数的曼哈顿距离c[i]=(x+y)/2;b[i]=(x-y)/2;//排序求中位数的曼哈顿距离d[i]=(x-y)/2;}sort(a,a+n);sort(b,b+n);double  x,y;ll sum=0;if(n%2==1)//求中位数{x=a[n/2];y=b[n/2];}else{x=(a[n/2]+a[n/2-1])/2;y=(b[n/2]+b[n/2-1])/2;}if((x+y)==(int)(x+y)&&(x-y)==(int)(x-y))//恰好中位数是整数{for(int i=0; i<n; i++){sum+=abs(c[i]-(int)x)+abs(d[i]-(int)y);}cout<<sum<<endl;}else{int A=(x+y);int B=(x-y);ll ans1=0,ans2=0,ans3=0,ans4=0;//不是整数的四种情况for(int i=0; i<n; i++){ans1+=max(abs(k[i]-(int)A),abs(q[i]-(int)B));}for(int i=0; i<n; i++){ans2+=max(abs(k[i]-(int)A-1),abs(q[i]-(int)B));}for(int i=0; i<n; i++){ans3+=max(abs(k[i]-(int)A-1),abs(q[i]-(int)B-1));}for(int i=0; i<n; i++){ans4+=max(abs(k[i]-(int)A),abs(q[i]-(int)B-1));}sum=min(min(min(ans1,ans2),ans3),ans4);cout<<sum<<endl;}return 0;
}