sol.cpp

经典算法实现题----士兵站队问题

#include<iostream.h>
#include<stdio.h>   
#include<stdlib.h> 
#include<fstream.h>
#include<math.h>
             //林宗明   060320081
template<class T>
int Partition(T a[],int p,int r)
{
	int i=p,j=r+1;
	T x=a[p];
	while(true)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j) break;
		int y=a[i];
  		a[i]=a[j];
        a[j]=y;
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

template<class T>
void QuickSort(T 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 count_Y(int data_Y[],int n)
{
	int count=0;
    QuickSort(data_Y,0,n-1);
    int midY=n/2;
    for(int i=0;i<n;i++)
		count=count+(int)fabs(data_Y[i]-data_Y[midY]);
    return count;
}

int count_X(int data_X[],int n)
{
	int count=0;
    QuickSort(data_X,0,n-1);
	for(int i=0;i<n;i++)
		data_X[i]=data_X[i]-i;
    int midX=0;
    QuickSort(data_X,0,n-1);
    midX=n/2;
    int mid=data_X[midX];
    if(mid<-10000)          
		mid=-10000;
    if(mid+n-1>10000)
        mid=10000-n+1;
    for(int j=0;j<n;j++)
        count=count+(int)fabs(data_X[j]-mid);
    return count;
}

void main()
{
	int count_XY=0;
    ifstream data_in("input.txt");
	ofstream data_out("output.txt");
    int n;
    data_in>>n;
    int* X=new int[n];
    int* Y=new int[n];
    for(int i=0;i<n;i++)      
		data_in>> X[i]>> Y[i];         
    count_XY=count_Y(Y,n)+count_X(X,n);
    data_out<<count_XY;
	data_in.close();
	data_out.close();
	delete X;
	delete Y;
}