poj 1862 Stripies/優先隊列，pojstripies
原題鏈接：http://poj.org/problem?id=1862
簡單題，貪心+優先隊列主要練習一下stl大根堆
寫了幾種實現方式寫成類的形式還是要慢一些。。。
手打的heap：
1：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cmath>
4 #include<iostream>
5 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 #include<cstdio>
2 #include<cstdlib>
3 #include<cmath>
4 #include<iostream>
5 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 #include<cstdio>
2 #include<cstdlib>
3 #include<cmath>
4 #include<iostream>
5 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_queue<double> ans
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cmath>
4 #include<queue>
5 #include<iostream>
6 int main(){
7 #ifdef LOCAL
8 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_queue<double> 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
