原題鏈接：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 }
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 }
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 }
4：
std::priority_queue<double> ans1 #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 }
?
和for的區別)
方法實例)
-職責鏈模式(Chain))
