題目意思： 給定m個圓的半徑，現在要求找到一個矩形使得每一個球都以地面相切，要求輸出最小的矩陣的長度
解題思路： 最小的圓排列問題，對於這樣的一個圖形我麼是轉化為坐標來計算，那麼我們需要做的三個步驟就是 1 遞歸去放入每一個圓 2 求出每一個圓的圓心的橫坐標 3計算最小的長度 。 具體過程見代碼分析：
代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n , m;
double r[10];//用來存儲每一個圓的半徑
double p[10];//存儲圓的橫坐標
double ans;
//求解第k個圓的橫坐標函數（也就是說，第k個圓很可能跟前面任何一個圓相切。這時，只要把各種情況得到取值全部算出，並把最大值 記錄下來）
//我們知道對於從左往右的所有的圓來說，圓心的橫坐標都是增大，不用考慮圓的大小，那麼對於k這個圓，它是最右邊的那麼我們找到最大的橫坐標才是它的橫坐標值
double Point(int k){
double R = 0;
for(int j = 1 ; j < k ; j++){
double tempr = p[j] + 2.0*sqrt(r[k]*r[j]);//兩個圓的距離 d = sqrt((r1+r2)^2 - (r1-r2)^2) 那麼有 d = 2.0*sqrt(r[k]*r[j]);
if(R < tempr)//更新為最大
R = tempr;
}
return R;
}
//計算當前的圓排列的長度
//p[i]-r[i],就是該圓最左邊的切線的橫坐標 p[i]+r[i]就是該圓最右邊的切線的橫坐標，那麼對於這個圓排列的長度就是最右邊的橫坐標減去最左邊的橫坐標
void Distance(){
double high , low;
high = 0 ; low = 0;
for(int i = 1 ; i <= m ; i++){
if(p[i]-r[i] < low) low = p[i] - r[i]; //更新最左邊的位置
if(p[i]+r[i] > high) high = p[i] + r[i]; //更新最右邊的位置
}
if(high - low < ans)
ans = high - low;//更新最小距離
}
//回溯搜索函數
void dfs(int k){
if(k > m)//圓放完後就是計算這個排列的長度
Distance();
else{
for(int j = k ; j <= m ; j++){
swap(r[k] , r[j]);//考慮放入k後,序列長度; 還要考慮繼第k個球之後,余下的m-k個球放入後,對整個序列的長度的影響.
double R = Point(k);
if(R+r[k]+r[1] < ans){//滿足條件繼續遞歸
p[k] = R;
dfs(k+1);
}
swap(r[k] , r[j]);//現場的恢復
}
}
}
//主函數
int main(){
scanf("%d" , &n);
while(n--){
scanf("%d" , &m);
memset(r , 0.0 , sizeof(r));
memset(p , 0.0 , sizeof(p));
for(int i = 1 ; i <= m ; i++)
scanf("%lf" , &r[i]);
p[1] = 0.0;//規定第一個點的橫坐標為0
ans = 999999999;
dfs(1);
printf("%.3lf\n" , ans);//輸出的格式
}
return 0;
}
作者：cgl1079743846
