ハフマンツリー---優先キュー(C++STL)

データ構造実験の二叉木六:ハフマン符号化Time Limit:1000 MS Memory Limit:65536 KB Submit Static Problem Description
文字の符号化方式はいろいろありますが、よく知られているASCII符号化のほか、ハフマン符号化(Huffman Coding)も符号化方式で、可変字長符号化です.この方法は,文字出現確率に完全に基づいて平均長が最も短い符号化を構築し,最適符号化と呼ぶ.ハフマン符号化は、データファイル圧縮によく用いられ、その圧縮率は通常20%〜90%である.あなたの任務はキーボードから入力した文字列に対してそのASCII符号化長とハフマン符号化長の比を求めることです.Input
入力データは複数のグループがあり、各グループのデータは1行で、符号化する文字列を表す.Output
対応する文字のASCII符号化長la,huffman符号化長lh,la/lhの値(小数点を1桁保持)は、データ間にスペース間隔である.Example Input
AAAAABCD THE_CAT_IN_THE_HAT Example Output
64 13 4.9 144 51 2.8 Hint
Author
xam
ハフマンツリー:最適なツリー(重み付きパス長が最も短いツリー).通常、左サブツリールートノードの重み<=右サブツリールートノードの重みを規定します.

#include
using namespace std;
int main()
{
    string a;
    while(cin>>a)
    {
        int v[1210];
    priority_queue<int, vector<int>, greater<int> > q;//    
    /*              ，         */
    memset(v,0,sizeof(v));
        int la = 8 *a.size();//8    
        for(int i=0;i//    
        }
        for(int i=0;i<200;i++)
        {
            if(v[i])
              {
                  q.push(v[i]);//  
              }
        }
        int lh = 0;
        while(!q.empty())
        {
            int n = q.top();//  
            q.pop();//      
            if(!q.empty())
            {
                int m = q.top();//  
                q.pop();//  
                int s = m+n;
                q.push(s);//  
                lh += s;
            }
        }
        printf("%d %d %.1lf
", la, lh, la*1.0/lh);
    }
    return 0;
}

ツリー-スタックの練習-フルーツのハフマンツリーをマージするTime Limit:1000 MS Memory Limit:65536 KB Submit Static Problem Description
一つの果樹園では、多くの果物がすべて打たれ、果物の種類によって異なる山に分かれている.すべての果物をたくさん合成することにした.合併するたびに、多くの場合、2つの果物を統合することができ、消費された体力は2つの果物の重量の和に等しい.すべての果物はn-1回の合併を経て、1山しか残っていないことがわかる.多くの場合、果物を合併する際に消費される体力は、合併するたびに消費される体力の和に等しい.これらの果物を家に運ぶのに力を入れなければならないので、果物を合併するときはできるだけ体力を節約しなければならないことが多い.各果物の重量が1であり、既知の果物の種類数と各果物の数を仮定すると、あなたの任務は合併の順序案を設計し、多くの体力を最小限に抑え、この最小の体力消費値を出力することです.例えば3種類の果物があり、数は1,2,9の順である.まず1、2スタックを統合することができ、新しいスタックの数は3で、体力を消費するのは3です.次に、新しいスタックを元の第3のスタックと統合し、新しいスタックを得、数は12であり、体力は12である.そのため、体力=3+12=15を多く消費します.15が最小の体力消費値であることが証明される.
Input
1行目は整数n(1<=n<=10000)であり、果物の種類数を表す.2行目はn個の整数を含み、スペースで区切られ、i番目のai(1<=ai<=20000)はi番目の果物の数である.
Output
出力には1つの整数、すなわち最小の体力消費値しか含まれない行が含まれます.入力データは、この値が2^31未満であることを保証します.
Example Input
3 1 2 9 Example Output
15 Hint
Author
趙利強
think:前の問題とほとんど同じですが、この問題は簡単です.

#include
using namespace std;
int main()
{
    int n, m;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int> > q;
        for(int i=0;iscanf("%d", &m);
            q.push(m);
        }
        int sum = 0;
        while(!q.empty())
        {
            int n = q.top();
            q.pop();
            if(!q.empty())
            {
                int m = q.top();
                q.pop();
                int s = m+n;
                q.push(s);
                sum += s;
            }
        }
        printf("%d
", sum);
    return 0;
}

次のテーマは、特別なピットは、WAが見えてからACになったのですが・・・ピットポイントは、複数組の入力、そして、データ範囲が十分に大きくなければなりません.long long int、そうしないと越えられません.Fence Repair Time Limit:2000 MS Memory Limit:65536 KB Submit Statistic Discuss Problem Description
Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the “kerf”, the extra length lost to sawdust when a sawcut is made; you should ignore it, too. FJ sadly realizes that he doesn\’t own a saw with which to cut the wood, so he mosies over to Farmer Don\’s Farm with this long board and politely asks if he may borrow a saw. Farmer Don, a closet capitalist, doesn\’t lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents. Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.
Input
Line 1: One integer N, the number of planks Lines 2..N+1: Each line contains a single integer describing the length of a needed plank
Output
Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts
Example Input
3 8 5 8 Example Output
34 Hint
Author

#include 
using namespace std;
int main()
{
   long long  int n;
    long long int m;
    priority_queue <long long int, vector<long long int>, greater<long long int> > q;
    while(~scanf("%lld", &n))
    {
    for(int i=0;iscanf("%d", &m);
       q.push(m);
    }
    m = 0;
    while(!q.empty())
    {
        long long int a = q.top();
        q.pop();
        if(!q.empty())
        {
            long long int b = q.top();
            q.pop();
            long long int c = a + b;
            q.push(c);
            m += c;
        }
    }
      printf("%lld
", m);
    }
    return 0;
}