Description
给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如下图所示。（注意，只要求圆和矩形框底边相切，不要求相邻圆都相切）
Input
输入为两行，第一行为一个整数n，即圆的个数；第二行为n个数，即圆的
Output
输出为一个浮点数，取到小数点后2位，即圆排列的最小长度
Sample Input 1
3 1 1 2
Sample Output 1
7.65
思路
他只给出半径，没给顺序，所以给他来个全排列。
假设大的圆的半径x，小的圆的半径y
根据勾股定理，那么矩形底边的那段长就是(x+y)*(x+y)-(x-y)*(x*-y)然后开根号
把所有这样的结果（1到2，2到3····一直到n-1到n）全部加起来，再加上第一个和最后一个圆的半径，就是底边的长了。
然后取最小的。还没剪枝就过了。。。。
好像是可以用剪枝来优化，（代码里没有）如果当前的排列的底边已经大于已经求得的最小值了，
那么可以直接剪枝（直接跳过该排序）
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int r[1000];//存放半径double calculate(int r[],int n,double minL){double x,y;//表示两个圆的半径double sum=0;for(int i=1;i<n;i++){//取大的半径为x，小的为yif(r[i]>r[i+1]){x=r[i];y=r[i+1];}else{y=r[i];x=r[i+1];}//两个圆的矩形边方向的距离sum+= sqrt((x+y)*(x+y)-(x-y)*(x-y));}sum+=r[1]+r[n];//加上开头和结束minL=min(minL,sum);return minL;
}int main(){cin>>n;double ans=DBL_MAX;//取一个无穷大for(int i=1;i<=n;i++){cin>>r[i];}do{ans=calculate(r,n,ans);}while(next_permutation(r+1,r+n+1));//全排列printf("%.2f",ans-0.005);//减去0.005来进行浮点数精度修正
}
