圆排列问题

题目链接：点击这里

回溯法AC代码：

#include<iostream>
#include<cstdio> 
#include<cmath>
#include<algorithm>

using namespace std;
const int N = 100;

int n;						// 圆的个数
double r[N];				// 每个圆的半径
double x[N];				// 每个圆心横坐标
double minlen;				// 最小圆排列长度，初始值为正无穷
double bestv[N];			// 最小圆排列的半径顺序

double center(int t)		// 得到第t个圆的圆心横坐标
{
	double tmp = 0;
	// 计算第t个圆与前面已排列圆(1~t-1)相切时的距离，取最大距离
    for(int i = 1; i < t; ++i)
    {
        double xvalue = x[i] + 2.0 * sqrt(r[i] * r[t]);
		if(xvalue > tmp)	tmp = xvalue;
    }
    return tmp;
}

void compute()						// 计算圆排列长度
{
    double low = 0, high = 0;
    for(int i = 1; i <= n; ++i)		// 寻找最左端与最右端的距离
	{
        if(x[i] - r[i] < low)	low = x[i] - r[i];
        if(x[i] + r[i] > high)	high = x[i] + r[i];
    }
    
    if(high - low < minlen)
	{
        minlen = high - low;
    	// for(int i = 1; i <= n; ++i)	bestv[i] = r[i];
    }
}

void Backtrack(int t)
{
    if(t > n)
    {
    	compute();
	}
    else
	{
        for(int i = t; i <= n; ++i)
		{
            swap(r[t], r[i]);
            double centerx = center(t);				// 计算第t个圆的横坐标
            if(centerx + r[1] + r[t] < minlen)
			{
                x[t] = centerx;						// 加入第t个圆
                Backtrack(t + 1);					// 搜索下一个圆
            }
            swap(r[t], r[i]);
        }
    }
}

int main()
{
	scanf("%d", &n);
    for(int i = 1; i <= n; ++i)	scanf("%lf", &r[i]);
    
    minlen = 1e9;
    Backtrack(1);
    
    printf("%.2f\n", minlen);
	// for(int i = 1; i <= n; ++i)	printf("%.2f ", bestv[i]);
	
	return 0;
}
           

center函数：

c e n t e r ( ) center() center() 计算圆在当前圆排列中的横坐标，由 x 2 = ( r 1 + r 2 ) 2 − ( r 1 − r 2 ) 2 x^2 = \sqrt{(r_1+r_2)^2-(r_1-r_2)^2} x2=(r1​+r2​)2−(r1​−r2​)2

​ 推导出 x = 2 ∗ r 1 ∗ r 2 x = 2 * \sqrt{r_1 * r_2} x=2∗r1​∗r2​

​。

为啥要把计算圆心坐标的公式放在一个for循环里面呢？我们很容易会有一个先入为主的思想，那就是后一个圆必然与排在它前一个位置的圆相切，其实排在任意位置的圆与其前或后的任意一个圆都有可能相切的，画个图就很清晰了。只要大小合适，目标圆就有可能与排列中的任意一个圆相切。

compute函数：

可以想象其中任意的一个圆无限大或无限小，无限大的话那其余的圆就可以统统忽略了。因为已知所有圆的 x [   ] x[\ ] x[ ] 和 r [   ] r[\ ] r[ ]，很容易求出每个圆的左右坐标，通过比较找出最小的左部坐标和最大的右部坐标，一减就是该圆排列的长度，然后把每次不同的排列长度相比较，找到更小的minlen就更新。