SGU 203 Hyperhuffman

题意：构造哈夫曼数，求出其中产生节点值的和
解题思路：裸优先队列（最小堆），渣渣只会堆
解题代码：
  1 // File Name: c.cpp
  2 // Author: darkdream
  3 // Created Time: 2013年09月04日 星期三 14时50分35秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #include<limits.h>
 25 #define  maxn  500005
 26 using namespace std;
 27 
 28 long long len, heapsize,a[maxn];
 29 long long LEFT(long long i )
 30 {
 31   return i*2;
 32 }
 33 long long RIGHT(long long i )
 34 {
 35    return i*2 +1;
 36 }
 37 long long PARENT(long long i )
 38 {
 39    return i/2;
 40 }
 41 void MIN_HEAPIFY(long long A[],long long i)
 42 {
 43   long long l = LEFT(i);
 44   long long r = RIGHT(i);
 45   long long fewest;
 46   if( l<= heapsize && A[l] < A[i])
 47       fewest = l;
 48   else fewest = i;
 49   if(r <= heapsize && A[r] < A[fewest])
 50       fewest = r;  //找出本节点以及其儿子节点最小的值的编号
 51   if(i != fewest)
 52     {
 53       long long temp = A[i];
 54       A[i] = A[fewest];
 55       A[fewest] = temp;
 56       MIN_HEAPIFY(A,fewest);//子树可能交换后不保持性质，使起保持性质
 57     }
 58 
 59 }
 60 void BUILD_MIN_HEAP(long long A[])
 61 {
 62    heapsize = len;
 63    //for(long long i = len/2 ;i >= 1;i --)
 64      // MIN_HEAPIFY(A,i);
 65 }
 66 long long HEAP_EXTRACT_MIN(long long A[])
 67 {
 68    long long MIN = A[1];
 69    A[1] = A[heapsize];
 70    heapsize = heapsize - 1;
 71    MIN_HEAPIFY(A,1);
 72    return MIN;
 73 }
 74 void HEAP_INCREASE_KEY(long long A[],long long i,long long key)
 75 {
 76   A[i] = key;
 77   while(i > 1 && A[PARENT(i)] > A[i] )
 78    {
 79      long long temp = A[PARENT(i)];
 80      A[PARENT(i)] = A[i];
 81      A[i] = temp;
 82      i = PARENT(i);
 83    }//向上更新
 84 
 85 }
 86 void MIN_HEAP_INSERT(long long A[],long long key)
 87 {
 88     heapsize = heapsize +1;
 89     A[heapsize] = INT_MAX;
 90     HEAP_INCREASE_KEY(A,heapsize,key);
 91 }
 92 int main(){
 93    //freopen("/home/plac/problem/input.txt","r",stdin);
 94    //freopen("/home/plac/problem/output.txt","w",stdout);
 95    long long t ; 
 96    scanf("%lld",&t);
 97    while(t--)
 98    {
 99       memset(a,0,sizeof(a));
100       scanf("%lld",&len);
101       for(long long i = 1;i <= len;i ++)
102           scanf("%lld",&a[i]);
103       BUILD_MIN_HEAP(a);
104       long long sum = 0 ;
105       for(long long i = 1;i <= len - 1;i ++)
106       {
107         long long tsum = HEAP_EXTRACT_MIN(a) + HEAP_EXTRACT_MIN(a); 
108         sum += tsum;
109         MIN_HEAP_INSERT(a,tsum);
110       }
111       printf("%lld
",sum);
112       if(t!= 0 )
113           printf("
");
114    }
115 
116 return 0;
117 }
View Code
没有梦想，何谈远方