post.cpp

这是一个邮局选址问题

#include<fstream.h>
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
ifstream input;
ofstream output;
void swap(int &x,int &y)
{
	int k=x;
	x=y;
	y=k;
}
int cut(int a[],int p,int r,int z)
{
	int i,j;
	j=r+1;
	i=p-1;
	while(true)
	{ 
		while(a[++i]<z);
		while(a[--j]>z);
		if(i>=j) break;
		swap(a[i],a[j]);
	}
		return j;
}
int partition(int a[],int p,int r)
{
	int i,j,x;
	i=p;
	j=r+1;
	x=a[p];
	while(true)
	{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=partition(a,p,r);
	quicksort(a,p,q-1);
	quicksort(a,q+1,r);
	}
}
int select(int a[],int p,int r,int k)
{
	if (r-p<75)
	{
		quicksort(a,p,r);
		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+5*i+2],a[p+i]);
	}
	int x=select(a,p,p+(r-p-4)/5,(r-p-4)/10);
	i=cut(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);
}

void  main()
{

int i,value,w,value1,value2,value3,k,l,m;
int total=0;
input.open("input.txt");
output.open("output.txt");
if (!input)
	{
		cout<<"error in opening input.txt\n";
		return;
	}
if (!output)
	{
		cout<<"error in opening output.txt\n";
		return;
	}
input>>i;
w=i;
int *a=new int[w];
int *b=new int[w];
for (k=0;k<w;k++)
input>>a[k]>>b[k];
l=select(a,0,w-1,(w+1)/2);
m=select(b,0,w-1,(w+1)/2);	    
for(k=0;k<i;k++)
	{   
		value=a[k]-l; 
	    value1=abs(value);
	    value2=b[k]-m;
	    value3=abs(value2);
		total=total+value1+value3;
	}
output<<total;
input.close();
output.close();
delete []a;
delete []b;
}