目录

题目链接：

思路：

代码：

---

题目链接：

P1099 - 输油管道问题 - New Online Judge (ecustacm.cn)

---

 

---

思路：

 因为主输油管道是由东向西的，

而每口油井要有一条输油管道和主输油管道连接（或南或北）

因此其实x坐标是干扰项，只要知道y坐标即可。

要求： i 个 输油管道之和最小，求此时 主输油管道的y坐标即是答案。

上图出自罗老师的博客：＜蓝桥杯软件赛＞零基础备赛20周--第8周第2讲--排序的应用-CSDN博客

注意！如果for循环是 [0，n），那么就是 sort（y，y+n） 和 m=y[n/2]

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int y[N];

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x>>y[i];
	}
	sort(y+1,y+n+1); //对n个y值排序
	int m=y[n/2+1]; //主输油管道的纵坐标,y是中位数
	int ans=0; //长度之和
	for(int i=1;i<=n;i++){
		ans+=abs(m-y[i]);
	}
	cout<<ans<<endl;
	return 0;
}