首页 > 其他 > 详细

4月14日

时间:2016-04-15 00:22:23      阅读:190      评论:0      收藏:0      [点我收藏+]

poj1862

题意:把一堆数两两合并为2*sqrt(m1*m2),求最终的最小值

分析:类似哈夫曼树,不过这次要先将大的合并,用一个优先队列维护即可,优先队列默认就是从大到小,即大顶堆

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <set>
 8 #include <map>
 9 #include <bitset>
10 #include <cmath>
11 #include <queue>
12 #include <stack>
13 using namespace std;
14 int n;
15 int main()
16 {
17     while(cin>>n)
18     {
19         priority_queue<double>que; //优先队列默认从大到小的顺序
20         for(int i=0;i<n;i++)
21         {
22             double x;
23             cin>>x;
24             que.push(x);
25         }
26         double t1,t2,t;
27         while(que.size()!=1)
28         {
29             t1=que.top();
30             que.pop();
31             t2=que.top();
32             que.pop();
33             t=2*sqrt(t1*t2);
34             que.push(t);
35         }
36         printf("%.3lf\n",que.top());
37     }
38     return 0;
39 }
View Code

 

4月14日

原文:http://www.cnblogs.com/wolf940509/p/5393393.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!