Preparing NOJ

圆排列问题

1000ms 65536K

Description:

     

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

所示。其最小长度如图所示

   

对于给定的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 NOJ1320

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet