dist.cpp

经典算法实现题--向量距离问题

#include<stdio.h>   
#include<stdlib.h>    
#include<iostream.h>
#include<fstream.h>
 //算法实现题1-9 向量距离问题
                       //林宗明  学号：060320081
void CountingSort(int a[],int n,int b[],int m)
{
	int i;
    int *c=new int[m+1];
    for(i=0;i<=m;i++)              
		c[i]=0;
	for(i=0;i<n;i++)
		c[a[i]]+=1;
	for(i=1;i<=m;i++)
		c[i]+=c[i-1];
	for(i=n;i>0;i--)
	{
		b[c[a[i-1]]-1]=a[i-1];
		c[a[i-1]]-=1;
	}
}
   
void  main()   
{   
	int k;
	ifstream params("input.txt"); 
	ofstream outtxt("output.txt"); 
	if(!params) 
	{
		cerr<<"input.txt file not open!"<<endl;
		params.close();
	}   
	int vi[2];  
	for (k=0;k<2;++k)      	 
		params>>vi[k]; 
	int m=vi[0];
	int n=vi[1];		  
	int *a=new int[m];		 
	int *b=new int[n];		
	for (k=0;k<m;++k)      			
		params>>a[k];  		 
	for (k=0;k<n;++k)      
		params>>b[k]; 
	int i,j;			
	int t=(m>=n?m:n);
	int *aa=new int[m];
	int *bb=new int[n]; 
	for(i=0;i<m;i++)
		a[i]+=t;
	CountingSort(a,m,aa,2*t);
	for(i=0;i<n;i++)
		b[i]+=t;
	CountingSort(b,n,bb,2*t);
	i=0;
	j=0;
	int distL,distR,dist,min;
	min=abs(bb[0]-aa[0]);
	if(min==0)
	{
		outtxt<<min<<endl; 
		outtxt.close();
		return;
	}
	if(bb[0]>aa[0])
	{
		while(i<m&&j<n)
		{
			if(bb[j]==aa[i])
			{
				min=0;
				break;
			}
			else if(bb[j]>aa[i])
				i++;
			else
			{
				distL=abs(bb[j]-aa[i-1]);
				distR=abs(bb[j]-aa[i]);
				dist=distL>distR?distR:distL;
				min=min>dist?dist:min;
				j++;
			}	
		}
	}
	else
	{
		while(i<m&&j<n)
		{
			if(aa[i]==bb[j])
			{
				min=0;
				break;
			}
			else if(aa[i]>bb[j])	
				j++;
			else
			{
				distL=abs(aa[i]-bb[j-1]);
				distR=abs(aa[i]-bb[j]);
				dist=distL>distR?distR:distL;
				min=min>dist?dist:min;
				i++;	
			}
		}
	}    
	outtxt<<min<<endl; 
	params.close();
	outtxt.close();
}