【题解-信息学奥赛一本通】1369：合并果子(fruit)

题目148. 合并果子题目描述在一个果园里达达已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。达达决定把所有的果子合成一堆。每一次合并达达可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。可以看出所有的果子经过 n−1 次合并之后就只剩下一堆了。达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家所以达达在合并果子时要尽可能地节省体力。假定每个果子重量都为 1并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使达达耗费的体力最少并输出这个最小的体力耗费值。例如有 3 种果子数目依次为 129。可以先将 1、2 堆合并新堆数目为 3耗费体力为 3。接着将新堆与原先的第三堆合并又得到新的堆数目为 12耗费体力为 12。所以达达总共耗费体力31215。可以证明 15 为最小的体力耗费值。输入输入包括两行第一行是一个整数 n表示果子的种类数。第二行包含 n 个整数用空格分隔第 i 个整数 ai是第 i 种果子的数目。输出输出包括一行这一行只包含一个整数也就是最小的体力耗费值。输入数据保证这个值小于 231。数据范围1 ≤ n ≤ 10000,1 ≤ ai≤ 20000时空限制1s / 64MB输入样例3 1 2 9输出样例15思路与算法简单证明每次合并两种最小数目的果子这样消耗体力之和最小。设合并n种果子所消耗的体力之和为F(n)果子种最小数目分别为a和b。F(n)F(n-1)ab。每次都先合并两种最小数目的果子可以看成先合并其他n-1种果子最后加上a和b。所以合并n-1种果子的局部最优解可以推导出n种果子的全局最优解。代码#includeiostream#includequeueusingnamespacestd;intn;intmain(){scanf(%d,n);priority_queueint,vectorint,greaterintheap;while(n--){intx;scanf(%d,x);heap.push(x);}intres0;while(heap.size()1){intaheap.top();heap.pop();intbheap.top();heap.pop();resab;heap.push(ab);}printf(%d,res);return0;}结果