post.cpp

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

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

void Swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
int Partion(int a[],int p,int r) 
{
	int i=p,
		j=r+1;

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

void QuickSort(int a[],int p,int r)  //快速排序
{
	if(p<r)
	{
		int q=Partion(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}
int SelectPartion(int a[],int p,int r,int k)  //求Select的划分基准 
	int i=p-1,
		j=r+1;
	while(1)
	{
		while(a[++i]<k);
		while(a[--j]>k);
		if(i>j)  break;
		Swap(a[i],a[j]);
	}
	return j;
}
int Select(int a[],int p,int r,int k)   //找中位数
{
	if(r-p<75)
	{
		QuickSort(a,p,r);  //n小于75时直接调用快速排序找中位数
		return a[p+k-1];
	}
	for(int i=0;i<=(r-p-4)/5;i++)
	{
		QuickSort(a,p+5*i,p+5*i+4); 
		Swap(a[p+i],a[p+5*i+2]);
	}
	int x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);
	i=SelectPartion(a,p,r,x);       
	int j=i-p+1;
	if(k<=j) return Select(a,p,i,k);
	else return Select(a,i+1,r,k-j);
}
int main()
{
	int n,x,y;
    ifstream input("input.txt");
	ofstream output("output.txt");
	input>>n;
	int *sx=new int[n+1],
	    *sy=new int[n+1];
	for(int i=0;i<n;i++)
	{
		input>>x>>y;
		if(x>=-10000&&x<=10000&&y>=-10000&&y<=10000)
		{
			sx[i]=x;
			sy[i]=y;
		}
	}
	input.close();
    int post_x=Select(sx,0,n-1,(n+1)/2);
    int post_y=Select(sy,0,n-1,(n+1)/2);
	long int dist=0;
	for(i=0;i<n;i++)
		dist=dist+abs(post_x-sx[i])+abs(post_y-sy[i]); 
	//计算各点到邮局的最短距离
	output<<dist<<endl;
	output.close();
	delete []sx;
	delete []sy;
	return 1;
}