一道贪心的水题，读完题目，直接把样例的三个数试一试，就知道怎么一种组合方式会产生最小的结果。
（让我想起了哈弗曼编码，用了优先队列）
1 #include<cstdio> 2 #include<queue> 3 #include<cmath> 4 using namespace std; 5 int n; 6 int main() 7 { 8 while(scanf("%d",&n)!=EOF) 9 { 10 priority_queue<double> q; 11 double tmp; 12 for(int i=1;i<=n;i++) 13 { 14 scanf("%lf",&tmp); 15 q.push(tmp); 16 } 17 for(int i=1;i<n;i++) 18 { 19 double x=q.top();q.pop(); 20 double y=q.top();q.pop(); 21 q.push( 2 * sqrt(x*y) ); 22 } 23 printf("%.3f\n",q.top()); 24 } 25 }
需要注意的是，POJ上那个double类型的printf，需要用%f而不是%lf，要不然就WA。
具体为什么是这样，那道题的discuss里有。
原文：http://www.cnblogs.com/dilthey/p/7241632.html