post.cpp

在一个按照东西和南北方向划分成规整街区的城市里

#include "stdlib.h"
#include "fstream.h"
#include "string.h"
#include "iostream.h"

//存贮X，Y坐标的线性表。
int x[10005],y[10005];
int nowXLen,nowYLen;

//交换程序
void swap(int& x,int& y)
{
	int temp=x;x=y;y=temp;
}

//选择排序,用于数目小于75时的找K小的数
void selectSort(int a[],int start,int end)
{
	int minPosition,minValue;
	for(int i=start;i<end;i++)
	{
		minPosition=i;minValue=a[i];
		for(int j=i+1;j<=end;j++)
		{
			if (a[j]<minValue)
			{
				minValue=a[j];
				minPosition=j;
			}
		}
		swap(a[i],a[minPosition]);
	}
}

//快速排序的分区函数
int Partition(int a[],int start,int end,int key)
{
	int i=start-1;
	int j=end+1;
	while (true)
	{
	    while(a[++i]<key);
		while(a[--j]>key);
		if(i>=j) break;
		swap(a[i],a[j]);
	}
	return j;
}

//线性时间找到K小的数
int select(int a[],int start,int end,int k)
{
	if (end-start<75)
	{
		selectSort(a,start,end);
		return a[start+k-1];
	};
	for (int i=0;i<=(end-start-4)/5;i++)
	{
		selectSort(a,start+5*i,start+5*i+4);
		swap(a[start+i],a[start+5*i+2]);
	}
	
	int x=select(a,start,start+(end-start-4)/5,(end-start-4)/10);
	int m=Partition(a,start,end,x);
	int p=m-start+1;
    if (k<=p) return select(a,start,m,k);
	else return select(a,m+1,end,k-p);
}


//
int main(int argc, char* argv[])
{
	ifstream fin("input.txt");
	ofstream fout("output.txt");
	nowXLen=0;nowYLen=0;
	fin>>nowXLen;
	nowYLen=nowXLen;
	for(int i=0;i<nowXLen;i++)
	{
		fin>>x[i];
		fin>>y[i];
	}
	
	int xmin,ymin;
    
	xmin=select(x,0,nowXLen-1,(nowXLen+1)/2);
	
	ymin=select(y,0,nowYLen-1,(nowYLen+1)/2);
	
	long totalLen;
	totalLen=0;
	////
	for (int j=0;j<nowYLen;j++)
	{
		totalLen=totalLen+abs(xmin-x[j])+abs(ymin-y[j]);
	}
	fout<<totalLen;
	
	
    return 0;
}