1. 问题
给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形的底边相切。圆排列问题要求从n个圆的所有排列中找出由最小长度的圆排列。
2. 解析
这个问题可以通过搜索求出圆的全排列，并且计算排列中每个圆圆心所在横坐标的位置，每个圆心所在的x坐标减去其半径来更新左端点，加上半径来更新右端点，右端点减去左端点来更新最小值，最后的答案就是最优值
下面是排列树的图形
我们可以通过下面两张图发现，最新的圆所在横坐标，并不一定是与他最近的圆所决定的，我们需要判断其与之前所有排列的圆相切之后，最靠右的横坐标，这才是其横坐标
同时我们发现
设X为新的圆的横坐标，Y为之前排列的某一个圆的横坐标,设Y所在圆半径为R1，X所在圆半径为R2
X=Y+sqrt((R1+R2)*(R1+R2)-(R1-R2)*(R1-R2));
化简后可得 X=Y+2.0*sqrt(R1*R2)
3. 设计
计算当前圆横坐标
1 double cal_center(int t){ 2 double centerx=0; 3 for(int i=0;i<t;i++){//取之前排列圆里面相切最大的x坐标，其余计算出来的坐标必定和之前某个圆的相交 4 centerx=max(centerx,center[i]+2.0*sqrt(r[t]*r[i])); 5 } 6 return centerx; 7 }
计算最后的长度
1 void cal(){//计算此排列下矩形长度 2 double left=0,right=0; 3 for(int i=0;i<n;i++){ 4 left=min(left,center[i]-r[i]); 5 right=max(right,center[i]+r[i]); 6 } 7 if(ans>right-left) { 8 ans=right-left; 9 for(int i=0;i<n;i++) dos[i]=r[i]; 10 } 11 return; 12 }
回溯法求搜索树
1 for(int i=x;i<n;i++){//回溯法排列树 2 swap(r[x],r[i]); 3 double y=cal_center(x); 4 if(y+r[1]+r[x]<ans) center[x]=y,dfs(x+1);//剪枝，若此时 圆心加半径的长度已经比最小长度大则没必要继续搜索 5 swap(r[x],r[i]); 6 }
4. 分析
对于搜索树其复杂度为O(n!)
最后计算长度需要O(n)
则其复杂度为O(n*n!)
5. 源码
1 #include <stdlib.h> 2 #include <time.h> 3 #include<stdio.h> 4 #include<cstdio> 5 #include<iostream> 6 #include<cmath> 7 #include<cstring> 8 #include<algorithm> 9 #include<bitset> 10 #include<set> 11 #include<deque> 12 #include<queue> 13 #include<vector> 14 //#include<unordered_map> 15 #include<map> 16 #include<stack> 17 using namespace std; 18 #define ll long long 19 #define ull unsigned long long 20 #define pii pair<int,int> 21 #define Pii pair<ll,int> 22 #define m_p make_pair 23 #define l_b lower_bound 24 #define u_b upper_bound 25 const int inf = 0x3f3f3f3f; 26 const ll linf = 0x3f3f3f3f3f3f3f3f; 27 const int maxn = 2e5 + 11; 28 const int maxm = 20; 29 const int mod = 1000000007; 30 const double eps = 1e-5; 31 inline ll rd() { ll x = 0, f = 1; char ch = getchar(); while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f; } 32 inline ll qpow(ll a, ll b, ll p) { ll res = 1; while (b) { if (b & 1) { res *= a; res %= p; }b >>= 1; a = a * a%p; }return res; } 33 inline ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a%b); } 34 //template<class T> void read(T&num) { char CH; bool F = false; for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar()); for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar()); F && (num = -num); } 35 //void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; }if (x > 9) print(x / 10); putchar(x % 10 + '0'); } 36 //iterator 37 //head 38 //priority_queue 39 //高斯消元 40 double ans,center[maxm];//center[maxm]全排列时指每个圆的圆心坐标 41 int n,r[maxm],dos[maxm]; 42 void cal(){//计算此排列下矩形长度 43 double left=0,right=0; 44 for(int i=0;i<n;i++){ 45 left=min(left,center[i]-r[i]); 46 right=max(right,center[i]+r[i]); 47 } 48 if(ans>right-left) { 49 ans=right-left; 50 for(int i=0;i<n;i++) dos[i]=r[i]; 51 } 52 return; 53 } 54 double cal_center(int t){ 55 double centerx=0; 56 for(int i=0;i<t;i++){//取之前排列圆里面相切最大的x坐标，其余计算出来的坐标必定和之前某个圆的相交 57 centerx=max(centerx,center[i]+2.0*sqrt(r[t]*r[i])); 58 } 59 return centerx; 60 } 61 void dfs(int x) 62 { 63 if(x==n){ 64 cal(); 65 return; 66 } 67 for(int i=x;i<n;i++){//回溯法排列树 68 swap(r[x],r[i]); 69 double y=cal_center(x); 70 if(y+r[1]+r[x]<ans) center[x]=y,dfs(x+1);//剪枝，若此时 圆心加半径的长度已经比最小长度大则没必要继续搜索 71 swap(r[x],r[i]); 72 } 73 } 74 int main() 75 { 76 n=rd(); 77 ans=inf; 78 for(int i=0;i<n;i++) r[i]=rd(); 79 // sort(r,r+n,greater<int>()); 感觉有序无序对于剪枝影响不大 80 dfs(0); 81 printf("%lf ",ans); 82 for(int i=0;i<n;i++) printf("%d ",dos[i]);//输出半径排列 83 puts(""); 84 return 0; 85 }
https://github.com/Tinkerllt/algorithm-work.git