题目链接

Stripies POJ - 1862

思路

假设一共有n个数，最终的结果为
$$ 2 \cdot a_1^{1/2} \cdot 2^{1/2} \cdot a_2^{1/4} \cdot 2^{1/4} \cdot a_3^{1/8} \cdot \cdot \cdot 2^{1/2^{n-2}} \cdot a_{n-1}^{1/2^{n -1}} \cdot a_{n}^{1/2^{n -1}} $$
所以每次应该选大的进行合并，a + b >= 2sqrt(ab) > min(a, b) 所以不需要优先队列， 排序即可。

ps：这个证明比较迷，笔者目前未发现比较好的数学证明。

时间复杂度

$$ O(Nlog(N)) $$

代码

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

using namespace std;

const int MAXN = 100 + 10;

double a[MAXN];

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &a[i]);// don't forget &
    }
    sort(a + 1, a + 1 + n);
    double now = a[n];
    for (int i = n - 1; i >= 1; i--) {
        now = 2 * sqrt(now * a[i]);
    }
    printf("%.3f", now);
    return 0;
}