• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Why so serious? --[NKU]schindlerlee

            2010年02月13日星期六.sgu203 二叉堆

            2010年02月13日星期六.sgu203 二叉堆
            sgu203:堆,根據一個文章生成單詞出現次數,求對這個文章進行霍夫曼編碼之后的文章長度。

            我郁悶,這個題想了半天,想了一個構建二叉樹,然后記錄葉子節點深度,之后用最大深度減去這
            個深度的方法。不過,我自己都覺得這個應該過不了。。。

            無意間看了一眼discuss,有一人的代碼寫了這么兩句
            a = heap.pop(),b = heap.pop();
            ans = ans + a + b;
            一拍大腿,原來如此啊,我咋沒想到。。。

            霍夫曼樹選擇兩個最小的加到新節點上,那么也就等于到這兩個小的節點的邊就被加到了新節點上。
            也就是,隨著新節點的繼續累計,這個兩個節點的權并未丟失。

            最后也就是,在拓展霍夫曼樹的時候,只要堆大小大于2,就累加最小的兩個點的值。

            然后更囧的事發生了,我手寫的堆超時了。。。。。
            我還用這個模板ac過pku3013,那個只能手寫堆才能過的dijkstra。
            我記得我這個堆的寫法是自己想的,當初看過一個stl中的make_heap,pop_heap,push_heap的調用,在
            http://support.microsoft.com/kb/157157/zh-cn
            其中有幾行是這樣的

            push_heap(Numbers.begin(), Numbers.end()) ;

            // you need to call make_heap to re-assert the
            // heap property
            make_heap(Numbers.begin(), Numbers.end()) ;

            現在一看,這幾句寫錯了啊。
            push_heap之后再make_heap復雜度就不對了啊。

            其實應該是在堆的末尾插入一個元素,沿著這個這個元素不斷上翻,達到維護堆的性質的目的,而不是調用
            heapify().
            可嘆阿,到今天才寫對第一個push_heap();
             1 
             2 
             3 const int N = 500100;
             4 #define L(x) ((x) << 1)
             5 #define R(x) (((x) << 1) + 1)
             6 #define P(x) ((x) >> 1)
             7 
             8 LL a[N],res; //a從1開始存儲
             9 int n;
            10 
            11 void heapify(int x)
            12 {
            13   int smallest = x,l = L(x),r = R(x);
            14   if (l <= n && a[l] < a[smallest]) { smallest = l; }
            15   if (r <= n && a[r] < a[smallest]) { smallest = r; }
            16   if (smallest != x) {
            17       swap(a[smallest],a[x]);
            18       heapify(smallest);
            19   }
            20 }
            21 
            22 LL pop()
            23 {
            24   swap(a[1],a[n--]);
            25   heapify(1);
            26   return a[n+1];
            27 }
            28 
            29 void make_heap()
            30 {
            31   for (int i = P(n); i >= 1; i--) {
            32       heapify(i);
            33   }
            34 }
            35 
            36 void push(LL x)
            37 {
            38   int i = n+1;
            39   for (a[++n] = x;i > 1 && a[P(i)] > x; i/= 2) {
            40       a[i] = a[P(i)];
            41   }
            42   a[i] = x;
            43 }
            44 
            45 int main()
            46 {
            47   int i,j,k;
            48   scanf("%d",&n);
            49   for (i = 1; i < n + 1; i++) {
            50       scanf("%I64d",a + i);
            51       //cin >> a[i];
            52   }
            53   make_heap();
            54   while (n > 1) {
            55       LL a = pop();
            56       LL b = pop();
            57       res += a + b;
            58       push(a + b);
            59   }
            60   cout << res << endl;
            61   return 0;
            62 }
            63 
            64 


            posted on 2010-02-13 02:20 schindlerlee 閱讀(1401) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久精品国产亚洲77777| 少妇人妻88久久中文字幕| 久久久噜噜噜久久熟女AA片| 久久精品无码午夜福利理论片| 国内精品久久久久影院一蜜桃| 久久精品9988| 性做久久久久久免费观看| 久久精品国产精品亚洲精品| 精品蜜臀久久久久99网站| 99久久国产亚洲高清观看2024 | 国内精品久久久久久野外| 91久久香蕉国产熟女线看| 伊人久久亚洲综合影院| 精品久久久久久久久午夜福利| 国产精品美女久久久久AV福利| 久久久午夜精品福利内容| 久久久女人与动物群交毛片 | 亚洲国产精品成人久久| 国产精品一区二区久久精品无码| 一本色综合久久| 99久久精品免费看国产一区二区三区| 亚洲国产天堂久久综合| 欧美激情精品久久久久| 伊人久久大香线蕉综合Av| 久久精品国产精品亚洲下载| 久久久久久久久久久久中文字幕| 深夜久久AAAAA级毛片免费看| 日本福利片国产午夜久久| 浪潮AV色综合久久天堂| 热99RE久久精品这里都是精品免费 | 久久精品国产清自在天天线| 久久精品水蜜桃av综合天堂| 久久受www免费人成_看片中文| 青青草国产成人久久91网| av午夜福利一片免费看久久| 国内精品久久久久影院薰衣草| 亚洲国产成人久久综合区| 久久精品不卡| 久久综合九色综合久99| 99久久精品国产一区二区三区| 秋霞久久国产精品电影院|