做网站 最好的开源cms,wordpress裁剪缩略图,邢台企业网站建设,四川招标采购网原题链接#xff1a;http://poj.org/problem?id1862 简单题#xff0c;贪心优先队列主要练习一下stl大根堆 写了几种实现方式写成类的形式还是要慢一些。。。 手打的heap#xff1a; 1#xff1a; 1 #includecstdio2 #includecstdlib3 #includecmathhttp://poj.org/problem?id1862 简单题贪心优先队列主要练习一下stl大根堆 写了几种实现方式写成类的形式还是要慢一些。。。 手打的heap 1 1 #includecstdio2 #includecstdlib3 #includecmath4 #includeiostream5 class Solution{6 public:7 static const int Max_N 110;8 int sz;9 double heap[Max_N];
10 inline void init(){
11 sz 0;
12 }
13 inline void push(double x){
14 int i sz;
15 while (i 0){
16 int p (i - 1) 1;
17 if (heap[p] x) break;
18 heap[i] heap[p];
19 i p;
20 }
21 heap[i] x;
22 }
23 inline double pop(){
24 double ret heap[0], x heap[--sz];
25 int i 0;
26 while ((i 1) 1 sz){
27 int a (i 1) 1, b (i 1) 2;
28 if (b sz heap[a] heap[b]) a b;
29 if (heap[a] x) break;
30 heap[i] heap[a];
31 i a;
32 }
33 heap[i] x;
34 return ret;
35 }
36 };
37 int main(){
38 #ifdef LOCAL
39 freopen(in.txt, r, stdin);
40 freopen(out.txt, w, stdout);
41 #endif
42 int n;
43 double a, b;
44 Solution ans;
45 ans.init();
46 scanf(%d, n);
47 while (n--){
48 scanf(%lf, a);
49 ans.push(a);
50 }
51 while (ans.sz 1){
52 a ans.pop(), b ans.pop();
53 ans.push(2 * sqrt(a * b));
54 }
55 printf(%.3lf, ans.pop());
56 return 0;
57 } View Code 2 1 #includecstdio2 #includecstdlib3 #includecmath4 #includeiostream5 struct Node{6 static const int Max_N 110;7 int sz;8 double heap[Max_N];9 Node() :sz(0){}
10 inline void push(double x){
11 int i sz;
12 while (i 0){
13 int p (i - 1) 1;
14 if (heap[p] x) break;
15 heap[i] heap[p];
16 i p;
17 }
18 heap[i] x;
19 }
20 inline double pop(){
21 double ret heap[0], x heap[--sz];
22 int i 0;
23 while ((i 1) 1 sz){
24 int a (i 1) 1, b (i 1) 2;
25 if (b sz heap[a] heap[b]) a b;
26 if (heap[a] x) break;
27 heap[i] heap[a];
28 i a;
29 }
30 heap[i] x;
31 return ret;
32 }
33 }ans;
34 int main(){
35 #ifdef LOCAL
36 freopen(in.txt, r, stdin);
37 freopen(out.txt, w, stdout);
38 #endif
39 int n;
40 double a, b;
41 scanf(%d, n);
42 while (n--){
43 scanf(%lf, a);
44 ans.push(a);
45 }
46 while (ans.sz 1){
47 a ans.pop(), b ans.pop();
48 ans.push(2 * sqrt(a * b));
49 }
50 printf(%.3lf, ans.pop());
51 return 0;
52 } View Code 3 1 #includecstdio2 #includecstdlib3 #includecmath4 #includeiostream5 const int Max_N 110;6 double heap[Max_N];7 int sz 0;8 void push(double x){9 int i sz;
10 while (i 0){
11 int p (i - 1) 1;
12 if (heap[p] x) break;
13 heap[i] heap[p];
14 i p;
15 }
16 heap[i] x;
17 }
18 double pop(){
19 double ret heap[0], x heap[--sz];
20 int i 0;
21 while ((i 1) 1 sz){
22 int a (i 1) 1, b (i 1) 2;
23 if (b sz heap[a] heap[b]) a b;
24 if (heap[a] x) break;
25 heap[i] heap[a];
26 i a;
27 }
28 heap[i] x;
29 return ret;
30 }
31 int main(){
32 #ifdef LOCAL
33 freopen(in.txt, r, stdin);
34 freopen(out.txt, w, stdout);
35 #endif
36 int n;
37 double a, b;
38
39 scanf(%d, n);
40 while (n--){
41 scanf(%lf, a);
42 push(a);
43 }
44 while (sz 1){
45 a pop(), b pop();
46 push(2 * sqrt(a * b));
47 }
48 printf(%.3lf, pop());
49 return 0;
50 } View Code 4 std::priority_queuedouble ans 1 #includecstdio2 #includecstdlib3 #includecmath4 #includequeue5 #includeiostream6 int main(){7 #ifdef LOCAL8 freopen(in.txt, r, stdin);9 freopen(out.txt, w, stdout);
10 #endif
11 int n;
12 double a, b;
13 scanf(%d, n);
14 std::priority_queuedouble ans;
15 while (n--){
16 scanf(%lf, a);
17 ans.push(a);
18 }
19 while (ans.size() 1){
20 a ans.top(), ans.pop();
21 b ans.top(), ans.pop();
22 ans.push(2 * sqrt(a * b));
23 }
24 printf(%.3lf, ans.top());
25 return 0;
26 } View Code 转载于:https://www.cnblogs.com/GadyPu/p/4456873.html
