C++ 搬水果贪心算法实现代码
C++搬水果贪心算法实现代码
(1)题目描述:
在一个果园里,小明已经将所有的水果打了下来,并按水果的不同种类分成了若干堆,小明决定把所有的水果合成一堆。每一次合并,小明可以把两堆水果合并到一起,消耗的体力等于两堆水果的重量之和。当然经过n‐1次合并之后,就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。
假定每个水果重量都为1,并且已知水果的种类数和每种水果的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值。例如有3种水果,数目依次为1,2,9。可以先将1,2堆合并,新堆数目为3,耗费体力为3。然后将新堆与原先的第三堆合并得到新的堆,耗费体力为12。所以小明总共耗费体力=3+12=15,可以证明15为最小的体力耗费值。
输入:
每组数据输入包括两行,第一行是一个整数n(1<=n<=10000),表示水果的种类数,如果n等于0表示输入结束,且不用处理。第二行包含n个整数,用空格分隔,第i个整数(1<=ai<=1000)是第i种水果的数目。
输出:
对于每组输入,输出一个整数并换行,这个值也就是最小的体力耗费值。输入数据保证这个值小于2^31。
样例输入:
3
912
0
样例输出:
15
(2)这种问题考虑到可以使用贪心算法(每次都将最小的一堆水果进行合并),问题与赫夫曼编码类似。代码也是根据Huffman编码算法的基础上的改动,实现代码为:
PS:代码只是实现其功能,没有优化。使用Vector作为容器,存放耗费的体力值,每执行一次Extract_MIN操作就会遍历一次Vector,实际当中效率是很低的,所以实际应用当中应该采用最小堆结构来存放耗费的体力值,这样会节省很多时间。
#include#include usingnamespacestd; /* *得到队列中的最小元素 */ intExtract_MIN(vector &v) { if(v.size()==0) return-1; inti=0,min_pos=0; vector ::iteratoriter=v.begin(); vector ::iteratormin_iter=v.begin(); for(;iter!=v.end();++iter) if((*iter)<(*min_iter)) min_iter=iter; intmin_value=*(min_iter); v.erase(min_iter); returnmin_value; } /* *计算过程,类似于构建哈夫曼树 */ intMoveFruit(intdata[],intn) { //将元素初始化到队列中 vector v; inti=0; for(i=0;i >n) { if(n==0) break; int*data=newint[n]; inti=0; for(;i >data[i]; cout< 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!