LFYZ-OJ ID: 1016 输油管道问题

分析

根据之前的证明，我们已经知道最佳输油管线的y位置就是所有油井y坐标序列的中位数，故解题过程为：

1. 读入n个y数据

2. 对n个y数据进行排序（升序或降序）

3. 求中位数zws

4. 计算输油管线的累加和sum+=abs(ypos[i]-zws)

因此该题的主体是排序。已知n的范围为1～10000，简单排序算法O(n^2)=1*10^8，这个数字接近CPU每秒的运算负载，极有可能超时。故需要更高效的排序算法，如快速排序和归并排序。下面提供快速排序的代码。

代码例程：快速排序

#include<iostream>

#include<cmath>

using namespace std;

int ypos[20001];							//存储油井的y坐标数组

void qsort(int Data[], int low, int high){  //快速排序

	int i=low, j=high, m=Data[(low+high)/2];

	while(i<=j){

		while(Data[i]<m)	i++;

		while(Data[j]>m)	j--;

		if(i<=j){

			int t=Data[i];

			Data[i]=Data[j];

			Data[j]=t;

			i++, j--;

		}

	}

    if(j>low)	qsort(Data, low, j);        //对右部分排序

	if(i<high)	qsort(Data, i, high);       //对左部分排序

}

int main(){

	int n, zws, sum=0;					    //zws为中位数

	scanf("%d", &n);

	for(int i=1; i<=n; i++){		        //读入并存储y坐标

		int xpos;

		scanf("%d%d", &xpos, &ypos[i]);

	}

	qsort(ypos, 1, n);					    //对y坐标进行快速排序

	if(n%2)		zws=ypos[n/2+1];	        //n为奇数或偶数

	else		zws=(ypos[n/2]+ypos[n/2+1])/2;

	for(int i=1; i<=n; i++)			        //计算管道长度

		sum+=abs(ypos[i]-zws);

	printf("%d", sum);

	return 0;

}