040320187.cpp

贪心算法球园排列问题

#include<iostream.h>
#include <fstream>
#include<math.h>
#include<queue>
# include <time.h>

using namespace std ;

//double countTime(const char flag = 'e');

class CircleNode{
   friend bool operator>(const CircleNode a,CircleNode b){
			return a.cleng>b.cleng;
		}
   public: 
		void Center();//求圆心坐标
	    void Compute();//求圆排列的长度
		void Swap(int k);		
		double *r;//记录当前圆排列中所有圆的半径
		double *x;//记录当前圆排列中所有圆的圆心坐标
		int end;//记录当前圆排列中最后一个圆的位置
		double cleng;//记录当前圆排列的长度
};

void CircleNode::Center()
{	double temp=0;
	for(int i=1;i<end;i++){
		double valuex=x[i]+2.0*sqrt(r[end]*r[i]);
    	if(valuex>temp) temp=valuex;
	}
	x[end]=temp;
}

void CircleNode::Compute()
{	
	double low=0,high=0;
	for(int i=1;i<=end;i++){
		if(x[i]-r[i]<low) low=x[i]-r[i];
		if(x[i]+r[i]>high) high=x[i]+r[i];
	}
	cleng=(high-low);
}


void CircleNode::Swap(int k){
	double temp=r[end];
	r[end]=r[k];
	r[k]=temp;
}


bool confine(CircleNode *N)//剪枝条件
{
  if (N->end<=2) return false;
  if ((N->r[N->end-2]<N->r[N->end-1]) && (N->r[N->end-1]<N->r[N->end])){
		return true;
  };
  if ((N->r[N->end-2]>N->r[N->end-1]) && (N->r[N->end-1]>N->r[N->end])){
		return true;
  };
  return false;
};
  
int main()
{
//countTime('s');
ifstream infile("input.txt");
	if(!infile)
	{cerr<<"open file input error!"<<endl;
	return -1;
	}
ofstream outfile("output.txt");
	if(!outfile)
	{cerr<<"open file output error!"<<endl;
	return -1;
	}

	int n;
	infile>>n;
	double *r=new double[n+1];
	for(int i=1;i<=n;i++)
		infile>>r[i];

//求最佳排列的过程
	priority_queue<CircleNode*,vector<CircleNode*>,greater<CircleNode*> > H;
	CircleNode *E,*N;
	double MINLENG=2147483647;

	for(i=1;i<n;i++){//第一层结点入队	
		E=new CircleNode;
        E->x=new double[n+1];
    	E->r=new double[n+1];	
	    E->x[1]=0;
	    E->end=1;
		for(int j=1;j<=n;j++)
			E->r[j]=r[j];
		E->Swap(i);
		E->cleng=2*E->r[1];	
		H.push(E);	
	} 	
	E=H.top();
	H.pop();
   // int member=0;
	while(true){
		for(int i=E->end+1;i<=n;i++){//中间结点的儿子们入队	
			N=new CircleNode;
	    	N->r=new double[n+1];
	    	N->x=new double[n+1];
		    for(int j=1;j<=n;j++){
			   N->x[j]=E->x[j];
			   N->r[j]=E->r[j];
			}
    	    N->end=E->end+1;	
	    	N->Swap(i);
			N->Center();			
		    N->Compute();
			if(confine(N)) continue;
			H.push(N);
		}
		
		E=H.top();
		H.pop();

		while(E->end==n){//到了叶结点，比较求出最佳排列

         /*   ++member;
			cout<<"第"<<member<<"个圆排列为： "<<endl;
			for(int k=1;k<=n;k++)
				cout<<E->r[k]<<" ";
			cout<<endl;
			cout<<"该圆排列的长度为："<<E->cleng<<endl;*/

			if(E->cleng<MINLENG)
				MINLENG=E->cleng;	
			if(H.empty()){
				outfile<<MINLENG;

		//		outfile<<"总用时为："<<countTime('e') << endl;

				return 0;
			}
			E=H.top();
			H.pop();
		}
	}

}
	
/*double countTime(const char flag){

	static clock_t startTime, endTime;

	double timeUsed = -1;

	if (flag == 's'){

		startTime = clock();

	}

	else{

		endTime = clock();

		timeUsed = endTime - startTime;

	}

	return timeUsed;

} */