P1090 NOIP 2004 提高组 合并果子 题解题目传送门: {[()]}这题很容易想到一个贪心每次取重量最小的两堆果子再取合并后重量最小的两堆果子直到只有一堆果子为止。接下来是证明证明贪心假设现在只有 3 堆果子果子的数量分别为 a,b,c假设 a≤b≤ca,b,c 的顺序与答案无关现在开始需要先取 a,b 一定是最优的。第一种情况先取 a,b最终答案为 (ab)(abc)2a2bc。第二种情况先取 a,c最终答案为 (ac)(abc)2ab2c。第二种情况先取 b,c最终答案为 (bc)(abc)a2b2c。现在需要比较 2a2bc,2ab2c,a2b2c 的大小关系。因为三个式子都含有 abc所以可以消掉 把三个式子同时减去 abc。现在问题就变成了比较 ab,ac,bc 的大小关系。因为 a≤b≤c所以 ab≤ac≤bc。所以第一种情况先取 a,b一定是最优的。再举个例子说明比如 a3,b5,c9。第一种情况先取 a,b的答案是 2a2bc25。第二种情况先取 a,c的答案是 2ab2c29。第三种情况先取 b,c的答案是 a2b2c31。通过比较也可以发现第一种情况先取 a,b是最优的。假设有 n(n3) 堆果子合并完 n−3 次之后还剩 3 堆果子可以用类似的方法证明取重量最小的两堆果子是最优的。因此取重量最小的两堆果子一定是最优的那么这题就可以用优先队列解决了priority_queue注意这题要用最小值优先算法构思1先输入存入优先队列2然后将队头两个元素相加再放入队列3最后输出代码在此附上#includebits/stdc.husingnamespacestd;intn;priority_queueint,vectorint,greaterinta;intmain(){cinn;for(inti1;in;i){intx;cinx;a.push(x);}intans0;while(a.size()1){intt0;ansa.top();ta.top();a.pop();ansa.top();ta.top();a.pop();a.push(t);}coutans;return0;}这题到此结束了有问题发评论区。点赞、收藏、订阅、关注、评论谢谢啦