题目描述
无
样例
无
算法1
(中位数的性质) $O(nlogn)$
我们易得性质:上下移动与左右移动可以分开进行,互不影响。
于是我们可以找出y坐标的中位数,用最小的代价先将所有点移到同一列上(这里令竖直方向为x轴方向,y轴为水平方向)。
接下来就是考虑如何将这些点彼此相邻,这里可以发现性质:彼此相邻安排后,这些点的相对位置是不会改变的,即如果一开始xi排在第i位,像这样安排过后,依然排在第i位。于是我们可以假设:排序后第一位的坐标为a,那么后面的点的坐标依次就是a+1,a+2,a+3.....a+n。于是我们可以给出移动次数的表达式,如下图:
即我们要找到一个a使得他们加起来最小,易得a等于他们的中位数!
至此,本题目得到解决
时间复杂度分析:找中位数时有排序,所以为nlogn;
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int x[10020],y[10020];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&x[i],&y[i]);
}
long long ans=0;
sort(y+1,y+1+n);
int mid=y[(1+n)>>1];//y坐标的中位数
for(int i=1;i<=n;++i){
ans+=abs(y[i]-mid);//统计答案
}
sort(x+1,x+1+n);//由于得先知道先后关系,所以排序
for(int i=1;i<=n;++i) x[i]-=i-1;//如上面的表达式
sort(x+1,x+1+n);
mid=x[(1+n)>>1];//中位数
for(int i=1;i<=n;++i) ans+=abs(x[i]-mid);
cout<<ans<<endl;
}
tql
66666