常用c++算法代码讲课讲稿.doc

《常用c++算法代码讲课讲稿.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、常用c++算法代码精品文档堆石子游戏的问题（多元Huffman编码）问题描述： 在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。 编程任务： 对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。 Input 测试数据的第1行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。

2、Output 输出最大总费用和最小总费用，用一空格隔开，每个答案一行。SampleInput 73 451312169522SampleOutput 593199代码： #include #include #includeusingnamespacestd;boolcmp(inta,intb) {    returna>b; }voidInsert(vector&f,intpos,intvalue) {    for(inti=f.size()

3、-1;i>pos;i--)    {        f[i]=f[i-收集于网络，如有侵权请联系管理员删除精品文档1];    }    f[pos]=value; }intFind(vectorf,intvalue) {    intpos=f.size()-1;    while(pos>=0&&f[pos]f) {    sort(f.begin(),f.e

4、nd());    intMax;    Max=0;    while(f.size()>=2)    {        intsum=f[f.size()-1]+f[f.size()-2];        Max=Max+sum;        f.resize(f.size()-1);        f[f.size()-1]=sum;    }    returnMax; }intMinNum(vectorf,intlen) {    sort(f.begin(),f.end(),cmp);

5、   intMin;    Min=0;    while(f.size()>=len)    {        intsum=0;        for(inti=f.size()-1;i>=f.size()-len&&i>=0;i--)        {            sum=sum+f[i];        }        Min=Min+sum;        f.resize(f.size()-len+1);        if(f.size()>收集于网络，如有侵权请联系管理员删除精品文档

6、len)        {            intpos=Find(f,sum);            Insert(f,pos,sum);        }        elseif(f.size()!=1)        {            f[f.size()-1]=sum;            for(inti=0;i

7、k;        }        else        {            break;        }    }    returnMin; }boolrun() {    intn,m;    if(!(cin>>n>>m))returnfalse;    vectorf(n);    for(inti=0;i>f[i];   }   intMax,Min;    Max=MaxNum(f);    while(f.size()%(m-

8、1)!=1)    {        f.push_back(0);    }    Min=MinNum(f,m);    cout<