soldier.cpp

是哨兵问题的实验

#include<stdlib.h>
#include <fstream.h>
#include <math.h>
#define size 10000
template<class T>
T RandomizedSelect(T a[],int p,int r,int k)
{
	if(p==r) return a[p];
	int i=RandomizedPartition(a,p,r),j=i-p+1;
	if(j==2&&a[p]==a[r]) return a[p];
	if(k<=j) return RandomizedSelect(a,p,i,k);
	else return RandomizedSelect(a,i+1,r,k-j);
}
template<class T>
int RandomizedPartition(T a[],int p,int r)
{
	int i=Random(p,r);
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
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;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
template<class T>
void RandomizedQuickSort(T a[],int p,int r)
{
	if(p<r)
	{
		int q=RandomizedPartition(a,p,r);
		RandomizedQuickSort(a,p,q-1);
		RandomizedQuickSort(a,q+1,r);
	}
}

inline int Random(int p,int r)
{  
	return p+rand()%(r-p+1);
}

template<class T>
inline void Swap(T& a,T& b)
{
	T temp=a;
	a=b;
	b=temp;
}
int Xstep(int x[],int n)
{
	int step=0;
	int m=(n+1)/2;
    RandomizedQuickSort(x,0,n-1);
	for(int i=0;i<n;i++)
		x[i]=x[i]-i;
    int mid=RandomizedSelect(x,0,n-1,m);
	for(i=0;i<n;i++)
		step+=abs(x[i]-mid);
    return step;
}
	
int Ystep(int y[],int ymax,int ymin)
{
	int step=0;
	while(ymax>ymin)
	{
		if(y[ymax]==y[ymin])
		{
			step+=y[ymax]*(ymax-ymin);
			ymax--;
			ymin++;
		}
		else if(y[ymax]>y[ymin])
		{
			step+=y[ymin]*(ymax-ymin);
			y[ymax]=y[ymax]-y[ymin];
			ymin++;
		}
		else
		{
			step+=y[ymax]*(ymax-ymin);
			y[ymin]=y[ymin]-y[ymax];
			ymax--;
		}
	}
	return step;
}
int main()
{
	ifstream ins("input.txt");
	ofstream outs("output.txt");
	int y[20001]={0};
	int a,b,c,e,n,ymax,ymin;
	ins>>n;
	int *x=new int[n];
	for(int i=0;i<n;i++)
	{
		ins>>x[i];
		ins>>e;
		if(i==0){ymax=e;ymin=e;}
		y[e+size]++;
		if(e>ymax) ymax=e;
		if(e<ymin) ymin=e;
	}	
	a=Xstep(x,n);
	b=Ystep(y,ymax+size,ymin+size);
	delete []x;
	c=a+b;
	cout<<a<<endl;
	cout<<b<<endl;
	outs<<c;
	return 0;
}