post.cpp

经典算法实现题--邮局选址问题

/* */
#include<fstream.h>
ifstream in("input.txt");
ofstream out("output.txt");

/* */
template <class T>
void BubbleSort(T a[], int n)		//冒泡排序
{
	for(int i=n; i>1; i--)
	  for(int j=0; j<i-1; j++)
		if(a[j] > a[j+1])
		  Swap(a[j], a[j+1]);
}
/* */
template <class T>
void Swap(T &a, T &b)
{
	T temp = a;
	a = b;
	b = temp;
}

/* */
template <class T>
int Partition(T a[], int p, int r, T x)
{
	int i = p-1, j = r+1;
	while(true)
	{
		while(a[++i]<x && i<=j);     //空语句
		while(a[--j]>x && j>=i);     //空语句
		if(i >= j) break;
		Swap(a[i], a[j]);
	}
	return j;
}

/* */
template <class T>
T Select(T a[], int p, int r, int k) //最坏情况下的线性时间选择算法
{
	if(r - p < 75)
	{
		BubbleSort(&a[p], r-p+1);
		return a[p+k-1];
	}
	else
	{
		for(int t=0; t<=(r-p-4)/5; t++)
		{
			int temp = 5*t;
			BubbleSort(&a[p+temp], 5);
			Swap(a[p+t], a[p+temp+2]);
		}
		T x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);
		int i = Partition(a, p, r, x), j = i-p+1;
		if(k <= j) return Select(a, p, i, k);
		else return Select(a, i+1, r, k-j);
	}
}

/* */
int main(void)
{
	int i, num, mx, my, sl = 0;
	in>>num;
	int *Sx = new int[num];
	int *Sy = new int[num];
	for(i = 0; i < num; i++)
	{
		in>>Sx[i];
		in>>Sy[i];
	}

	mx = Select(Sx, 0, num-1, (num+1)/2);	//选择X方向的坐标中位数
	my = Select(Sy, 0, num-1, (num+1)/2);	//选择Y方向的坐标中位数

	for(i = 0; i < num; i++)
	{
		if(mx >= Sx[i]) sl += mx - Sx[i];
		else sl += Sx[i] - mx;
		if(my >= Sy[i]) sl += my - Sy[i];
		else sl += Sy[i] - my;
	}

	out<<sl;

	return 0;
}