soliders.cpp

设计一个算法

// soliders.cpp : Defines the entry point for the console application.
//
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include<iostream.h>


void quicksort(int data[],int first,int last);
int partion(int data[],int first,int last);
int stepX(int data[],int k);
int stepY(int data[],int k);
void swap(int &a,int &b);
void main()
{
	int k;
	int step;
	ifstream fin("input.txt");
	ofstream fout("output.txt");
	fin>>k;
	int *x=new int[k];
	int *y=new int[k];
	for(int i=0;i<k;i++)
		fin>>x[i]>>y[i];
	quicksort(x,0,k-1);
	quicksort(y,0,k-1);
	step=stepY(x,k)+stepX(y,k);
    fout<<step;
}
void quicksort(int data[],int first,int last)
{
	if(first<last)
	{
		int mid=partion(data,first,last);
		quicksort(data,first,mid-1);
		quicksort(data,mid+1,last);
	}
}
int partion(int data[],int first,int last)
{
	srand(last-first+1);
	int p=first+rand()%(last-first+1);
	swap(data[p],data[first]);
	int i=first,j=last+1;
	int x=data[first];
	while(true)
	{
		while(data[++i]<x);
		while(data[--j]>x);
		if(i>=j)
			break;
		swap(data[i],data[j]);
	}
	data[first]=data[j];
	data[j]=x;
	return j;
}
int stepX(int data[],int k)
{
	int count=0;
	int midy=k/2;
	for(int n=0;n<k;n++)
		count=count+abs(data[n]-data[midy]);
	return count;
}
int stepY(int data[],int k)
{
	int count=0;
	for(int m=0;m<k;m++)
		data[m]=data[m]-m;
	int midx=0;
	quicksort(data,0,k-1);
	midx=k/2;
	int bound=data[midx];
	if(bound<-10000)
		bound=-10000;
	if(bound+k-1>10000)
		bound=10000-k+1;
	for(int n=0;n<k;n++)
		count=count+abs(data[n]-bound);
	return count;
}
void swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}
void bubblesort(int a[],int n)
{
	for(int i=n;i>1;i--)
		for(int j=0;j<i-1;j++)
			if(a[j]>a[j+1])
				swap(a[j],a[j+1]);
}