企业官网建设流程全解析

P1090 NOIP 2004 提高组 合并果子 题解

题目传送门: <{[()]}>

这题很容易想到一个贪心：每次取重量最小的两堆果子，再取合并后重量最小的两堆果子，直到只有一堆果子为止。

接下来是证明

证明贪心

假设现在只有 3 堆果子，果子的数量分别为 a,b,c，假设 a≤b≤c（a,b,c 的顺序与答案无关），现在开始需要先取 a,b 一定是最优的。

第一种情况：先取 a,b，最终答案为 (a+b)+(a+b+c)=2a+2b+c。

第二种情况：先取 a,c，最终答案为 (a+c)+(a+b+c)=2a+b+2c。

第二种情况：先取 b,c，最终答案为 (b+c)+(a+b+c)=a+2b+2c。

现在需要比较 2a+2b+c,2a+b+2c,a+2b+2c 的大小关系。

因为三个式子都含有 a+b+c，所以可以消掉 把三个式子同时减去 a+b+c。

现在问题就变成了比较 a+b,a+c,b+c 的大小关系。

因为 a≤b≤c，所以 a+b≤a+c≤b+c。

所以第一种情况（先取 a,b）一定是最优的。

再举个例子说明，比如 a=3,b=5,c=9。

第一种情况（先取 a,b）的答案是 2a+2b+c=25。

第二种情况（先取 a,c）的答案是 2a+b+2c=29。

第三种情况（先取 b,c）的答案是 a+2b+2c=31。

通过比较也可以发现第一种情况（先取 a,b）是最优的。

假设有 n(n>3) 堆果子，合并完 n−3 次之后，还剩 3 堆果子，可以用类似的方法证明取重量最小的两堆果子是最优的。

因此，取重量最小的两堆果子一定是最优的

那么这题就可以用优先队列解决了（priority_queue）

注意：这题要用最小值优先

算法构思

1：先输入存入优先队列

2：然后将队头两个元素相加，再放入队列

3：最后输出

代码在此附上：

#include<bits/stdc++.h>usingnamespacestd;intn;priority_queue<int,vector<int>,greater<int>>a;intmain(){cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;a.push(x);}intans=0;while(a.size()>1){intt=0;ans+=a.top();t+=a.top();a.pop();ans+=a.top();t+=a.top();a.pop();a.push(t);}cout<<ans;return0;}

这题到此结束了，有问题发评论区。（点赞、收藏、订阅、关注、评论，谢谢啦！）