企业官网建设流程全解析

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

此文章在洛谷上同步发表

题目大意

题目传送门
现在有n nn堆果子，每堆果子的重量为a i a_iai​，你要进行n − 1 n - 1n−1次合并。每次合并会把两堆果子合并成一堆果子，合并需要花费的体力为这两堆果子的重量之和，合并后果子的重量也为这两堆果子的重量之和。现在让你求出n − 1 n - 1n−1次合并花费的最小总体力。

思路

贪心思路

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

证明过程

现在就要证明这个贪心，这里不妨先证明小范围贪心正确，再证明推导到大范围正确，就可以证明这个贪心正确。

step 1: 证明小范围贪心正确

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

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

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

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

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

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

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

因为a ≤ b ≤ c a\le b \le ca≤b≤c，所以a + b ≤ a + c ≤ b + c a + b \le a + c \le b + ca+b≤a+c≤b+c。

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

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

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

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

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

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

step 2: 证明推导到大范围也正确

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

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

代码实现

选择priority_queue及使用方法

现在需要一种数据结构，能动态找到数据结构中最小值和次小值，并删除他们，再插入他们的和。

我这里采用的是 stl 库中的priority_queue（优先队列，也被称为堆），可以在O ( log ⁡ n ) O( \log n)O(logn)的时间复杂度内插入、查询优先队列中最大 / 最小值、删除优先队列中最大 / 最小值。

priority_queue的使用方法如下。

//定义方法#include<queue>//需要的头文件priority_queue<int>q1;//定义一个大根堆，查询和插入的是最大值priority_queue<int,vector<int>,greater<int>>q1;//定义一个小根堆，查询和插入的是最小值//使用方法q1.push(7);//往大根堆内插入一个值7q1.push(4);//插入4q1.push(12);//插入12q1.top();//查询大根堆内的最大值，此时返回值为12q1.pop();//删除大根堆内的最大值（删除12），没有返回值q1.size();//查询优先队列数的个数，此时返回值为2q1.top();//此时的最大值变成了7，所以返回7//小根堆的使用方法与大根堆的使用方法一样q2.push(9);//插入一个数9q2.top();//查询小根堆内最小值，返回9q2.push(1);//插入1q2.pop();//删除小根堆内最小值（删除1），同样没有返回值q2.push(3);//插入3q1.size();//查询优先队列数的个数，此时返回值为2q2.top();//此时小根堆内的值为3和9，返回3

算法流程

输入输出我就不在这里说了，请读者自行思考。
1. 定义优先队列（小根堆）。
2. 将每堆果子的重量放进优先队列。
3. 取出小根堆中最小值和次小值，统计答案，放入他们的和。
4. 重复步骤三，直到只有一堆果子。

Code（只展示关键代码）

priority_queue<int,vector<int>,greater<int>>q;//1.定义小根堆//2.将每堆果子的重量放进优先队列//我在这里不放了，请读者自行思考longlongsum=0;while(q.size()>1){//4.重复步骤三，直到只有一堆果子。inta1=q.top();q.pop();inta2=q.top();q.pop();//取出a1和a2，即最小值和次小值sum+=a1+a2;//统计答案q.push(a1+a2);//放入他们的和}