Greedy:Stripes(POJ 1826)

　　　　　　　　　　　　　　　　新生物

　　题目大意：给你一堆数，两两结合，答案为2*sqrt(x1*x2)，问组合成一个数时，最小的量？

　　超级无敌大水题，排序或者用堆都可以，反正就是优先组合大的，让根号一直把大数开根降低整体的大小

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 #include <math.h>
 5 
 6 using namespace std;
 7 
 8 typedef int Heap, Position;
 9 static Heap Stripes[101];
10 
11 static int Heap_size = 0;
12 void Insert(const int, Position);
13 int Delete_Max(void);
14 
15 void Insert(const int item, Position pos)
16 {
17     Position s, pr;
18 
19     for (s = pos; s > 1; s = pr)//大元素上滤
20     {
21         pr = s % 2 == 0 ? s >> 1 : (s - 1) >> 1;
22         if (Stripes[pr] < item)
23             Stripes[s] = Stripes[pr];
24         else break;
25     }
26     Stripes[s] = item;
27 }
28 
29 int Delete_Max(void)
30 {
31     int max = Stripes[1], tmp = Stripes[Heap_size--];
32     Position pr = 1, s1, s2, s;
33 
34     for (; pr <= Heap_size;)
35     {
36         s1 = pr << 1; s2 = s1 + 1;
37         if (s2 <= Heap_size)
38         {
39             s = Stripes[s1] > Stripes[s2] ? s1 : s2;
40             Stripes[pr] = Stripes[s];
41             pr = s;
42         }
43         else
44         {
45             if (s1 <= Heap_size)
46             {
47                 Stripes[pr] = Stripes[s1]; 
48                 pr = s1;
49             }    
50             break;
51         }
52     }
53     Insert(tmp, pr);
54     return max;
55 }
56 
57 int main(void)
58 {
59     int n,tmp;
60     double ans = 0;
61 
62     while (~scanf("%d", &n))
63     {
64         for (int i = 0; i < n; i++)
65         {
66             scanf("%d", &tmp);
67             Insert(tmp, ++Heap_size);
68         }
69         ans = (double)Delete_Max();//处理初始情况
70         for (int i = 1; i < n; i++)
71             ans = 2 * sqrt(ans*(double)Delete_Max());
72         printf("%.3f", ans);
73     }
74     return 0;
75 }

实在是太简单，我自己用自己写的堆实现了一下，数据量也很小，才100，洪水不解释