这三题都是哈夫曼树的应用,使用了STL中的优先队列 priority_queue,即在每次插入后都会保证队列中的数按优先级有序.
关于priority_queue<int,vecto<int>r,
#include <iostream> #include <queue> #include <cstdlib> #include <cstdio> #include <algorithm> using namespace std; int cmp(const void *a,const void *b); int main(){ string line; while(1){ getline(cin,line); if(line=="END")break; priority_queue<int ,vector<int>,greater<int> > qu; //对字符数组排序并将字符个数依次放入优先队列中 sort(line.begin(),line.end()); char c=line[0]; int times=0; for(int i=0;i<line.length();i++){ if(line[i]==c)times++; else{ qu.push(times); c=line[i]; times=1; } } qu.push(times); int oldLen=line.length()*8; int newLen=0; int a,b; if(qu.size()==1)newLen=qu.top(); while(1){ a=qu.top(); qu.pop(); if(qu.empty())break; b=qu.top(); qu.pop(); newLen+=a+b;//这一步很巧,因为编码长度和其在树中的层数相关 qu.push(a+b); } printf("%d %d %.1f\n",oldLen,newLen,oldLen*1.0/newLen); } return 0; }ZOJ 2399
这一题比上一题更赤裸裸了..只是注意下数据类型是long long和处理只有一个数的时候的情况
#include <iostream> #include <queue> #include <cstdio> using namespace std; int main(){ int n; int nCase; scanf("%d",&nCase); for(int i=0;i<nCase;i++){ scanf("%d",&n); priority_queue<long long,vector<long long>,greater<long long> > qu; while(n-->0){ long long x; scanf("%lld",&x); qu.push(x); } long long a=0,b=0; long long res=0; if(qu.size()==1)res=qu.top(); while(1){ a=qu.top(); qu.pop(); if(qu.empty())break; b=qu.top(); qu.pop(); res+=a+b; qu.push(a+b) ; } printf("%lld\n",res); if(i!=nCase-1)printf("\n"); } return 0; }
POJ 3253 锯木条,将一跟长度为L的木条按指定长度锯成N段,每次锯长度为l的木条花费l cents.分析题意,长度较长应该经过较少的切割次数后得到,类比哈夫曼树出现频度较高的字符编码较短,这题用哈夫曼编码的思路即可解决.
#include <iostream> #include <queue> using namespace std; int main(){ int n; while(cin>>n){ priority_queue<int,vector<int>,greater<int> > qu; while(n-->0){ int x; cin>>x; qu.push(x); } int a=0,b=0; long long res=0; while(1){ a=qu.top(); qu.pop(); if(qu.empty())break; b=qu.top(); qu.pop(); res+=a+b; qu.push(a+b) ; } cout<<res<<endl; } return 0; }