使用C语言实现给定n个圆的整数半径序列，将这些圆放到一个矩形框中，每个圆都与矩形框的底边相切，则圆的不同排列会得到不同的排列长度，如下图： 1.jpg 注意：因为圆的半径可能很大，也可能很小，也许会有这种情况出现： 2.jpg 要求找到使得排列长度最小的n个圆的排列。 输入格式: 第一行输入n值（1≤n≤10）。 第二行输入n个圆的整数半径序列。 输出格式: 第一行输出最小的排列长度，精确到小数点后两位，第三位按四舍五入方式处理。 第二行输出该排列对应的半径序列，各半径之间用一个空格分隔。为方便处理，最末位半径后面存在一个空格。 输入样例1: 3 3 3 3 输出样例1: 18.00 1 2 3 输入样例2: 5 1 3 5 7 9 输出样例2: 44.97 1 4 2 5 3

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 10

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int main() {
    int n, r[MAXN];
    double x, y, w, h, L = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &r[i]);
        L += 2 * r[i];
    }
    qsort(r, n, sizeof(int), cmp);
    x = y = w = h = r[0];
    for (int i = 1; i < n; i++) {
        double L1 = 2 * (w + h + r[i]); // 圆放在右侧的周长
        double L2 = 2 * (w + h + r[i] * sqrt(2)); // 圆放在下方的周长
        if (L1 < L2 || fabs(L1 - L2) < 1e-8 && w - h < 1e-8) { // 选择放在右侧
            x = x + w + r[i];
            y = y + r[i];
            w = w + r[i];
            L += L1;
        } else { // 选择放在下方
            x = x + r[i];
            y = y + h + r[i];
            h = h + r[i];
            L += L2;
        }
    }
    printf("%.2f\n", L);
    for (int i = 0; i < n; i++) {
        printf("%d ", r[i]);
    }
    printf("\n");
    return 0;
}

时间复杂度为 $O(n\log n)$，其中 $\log n$ 是排序的时间复杂度。