Preparing NOJ

圆排列问题

1000ms 65536K

Description:

 

 

    给定n个大小不等的圆c1 , c2 , , cn ,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3,且所给的3 个圆的半径分别为112时,这3个圆的最小长度的圆排列如图所示。其最小长度为2 + 4  

 

                                        

解圆排列问题的一个随机化算法如下。

void Circle_search(int *x)

{

random_perm(x);

found=true;

while(found){

found=false;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if(swap(x[i],x[j]) reduces length){

swap(x[i],x[j]);

found=true;}

}

}

其中,random_perm(x)产生x 的一个随机排列

根据上述算法框架,设计一个随机化算法,对于给定的n个圆,计算n个圆的最佳排列方案,使其长度尽可能小。

Input:

 输入的第一行有1个正整数n (1n20)。接下来的1行有n个数,表示n个圆的半径。

Output:

 

输出计算出的最小圆排列的长度

Sample Input:

3
1 1 2 

Sample Output:

7.65685

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1345

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet