[HDOJ5350]MZL's munhaff function-白红宇

[HDOJ5350]MZL's munhaff function

阅读量：4986 次

发布时间：2019-06-12

本文共 1460 字，大约阅读时间需要 4 分钟。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5350

手写堆

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 #include 
                    
                     17 #include 
                     18 #include 
                      
                       19 20 using namespace std;21 22 const int maxn = 100010;23 const int INF = 2147483647;24 int heap[maxn];25 int pos;26 27 void init() {28 pos = 0;29 memset(heap, 0, sizeof(heap));30 heap[0] = -INF;31 }32 33 void push(int x) {34 int i = ++pos;35 for(; heap[i>>1] > x; i>>=1) {36 heap[i] = heap[i>>1];37 }38 heap[i] = x;39 }40 41 void pop() {42 if(pos == 0) return;43 int child = 1;44 int i = 1;45 int last = heap[pos--];46 for(; i<<1 <= pos; i=child) {47 child = i<<1;48 if(child != pos && heap[child] > heap[child+1]) {49 ++child;50 }51 if(last > heap[child]) {52 heap[i] = heap[child];53 }54 else {55 break;56 }57 }58 heap[i] = last;59 }60 61 int n;62 63 int main() {64 int T_T;65 init();66 scanf("%d", &T_T);67 while(T_T--) {68 scanf("%d", &n);69 pos = 0;70 int tmp;71 int nn = n;72 while(nn--) {73 scanf("%d", &tmp);74 push(tmp);75 }76 long long ans = 0;77 int a, b;78 while(n-- > 1) {79 a = heap[1], pop();80 b = heap[1], pop();81 tmp = a + b;82 push(tmp);83 ans += tmp;84 }85 printf("%I64d\n", ans);86 }87 return 0;88 }