post.cpp

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

#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

inline void Swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

int Partition(int a[], int p, int r)
{
	int i = p;
	int j = r + 1;
	int x = a[p];
	while(true)
	{
		while(i<r && a[++i] < x);
		while(j>p && a[--j]>=x);
		if(i >= j) break;
		Swap(a[i],a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}

int RandomizedPartition(int a[], int p, int r)
{
	srand(time(0));
	int i = rand()%(r - p + 1) + p;
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
/*
void QuickSort(int a[], int p, int r) 
{
	if(p < r)
	{
		int q = Partition(a, p, r);
		QuickSort(a, p, q-1);
		QuickSort(a, q+1, r);
	}
}
*/
int RandomizedSelect(int a[], int p, int r, int k) //选取第k小元素
{
	if(p==r) return a[p];
	int i = Partition(a, p, r);
	int j = i - p + 1;
	if(k <= j) return RandomizedSelect(a, p, i, k);
	else       return RandomizedSelect(a, i+1, r, k-j);
}

int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");

	int n;
	in>>n;
	int *x = new int[n];
	int *y = new int[n];
	int middle = (int)n/2 + 1; //中位数,第middle小元素
	 
	for(int i=0; i<n; i++)
	{
		in>>x[i];
		in>>y[i];

	}
	
	//求邮局的x,y坐标
	int postX = RandomizedSelect(x,0,n-1,middle);
	int postY = RandomizedSelect(y,0,n-1,middle);
	//求最小距离
	int distance = 0;
	int dx,dy;
	for(int m=0; m<n; m++)
	{
		dx = abs(x[m] - postX);
		dy = abs(y[m] - postY);
		distance += (dx + dy);
	}
	delete []x;
	delete []y;
	out<<distance<<endl;
	return 0;
}