二话不说先上代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int x,y[10001];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&x,&y[i]);
}
sort(y+1,y+n+1);
int mid;
if(n%2==0){
mid=(y[n/2]+y[n/2+1])/2;
}else
{
mid=y[n/2+1];
}
int sum=0;
for(int i=1;i<=n;i++){
sum+=abs(y[i]-mid);
}
cout<<sum<<endl;
return 0;
}
思路&证明
这个题超简单啊……哈哈,不过我看题解区竟然有用模拟退火的的大佬??orzorz,蒟蒻只好在自己的地盘发一个题解……
本题主要思路是中位数。啊没错就是把所有y坐标给他排个序然后求中位数就完事了!
为什么这是对的呢?为什么是中位数而不是平均数呢?
首先我们要明确一件事:x坐标完全没有用。因为我们的主输油管道可以无限长。
接下来对y坐标下手,我们发现,题意可以翻译为:对一个有限的序列,求一个值使得这个值与序列中各值的差的绝对值的和最小。
这不就是中位数吗???
至于这个的具体证明,推荐一篇博文:中位数定理
所以直接求中位数就好了呀!