POJ 1862

一道贪心的水题，读完题目，直接把样例的三个数试一试，就知道怎么一种组合方式会产生最小的结果。

（让我想起了哈弗曼编码，用了优先队列）

 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
",q.top());
24     }
25 }

需要注意的是，POJ上那个double类型的printf，需要用%f而不是%lf，要不然就WA。

具体为什么是这样，那道题的discuss里有。