洛谷P1090 [NOIP 2004 提高组] 合并果子 题解

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≤ca , 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(ab)(abc)2a2bc。第二种情况先取a , c a, ca,c最终答案为( a c ) ( a b c ) 2 a b 2 c (a c) (a b c) 2a b 2c(ac)(abc)2ab2c。第二种情况先取b , c b, cb,c最终答案为( b c ) ( a b c ) a 2 b 2 c (b c) (a b c) a 2b 2c(bc)(abc)a2b2c。现在需要比较2 a 2 b c , 2 a b 2 c , a 2 b 2 c 2a 2b c,2ab 2c,a2b2c2a2bc,2ab2c,a2b2c的大小关系。因为三个式子都含有a b c a b cabc所以可以消掉 把三个式子同时减去a b c a b cabc。现在问题就变成了比较a b , a c , b c a b,a c,bcab,ac,bc的大小关系。因为a ≤ b ≤ c a\le b \le ca≤b≤c所以a b ≤ a c ≤ b c a b \le a c \le b cab≤ac≤bc。所以第一种情况先取a , b a, ba,b一定是最优的。再举个例子说明比如a 3 , b 5 , c 9 a 3, b 5, c 9a3,b5,c9。第一种情况先取a , b a,ba,b的答案是2 a 2 b c 25 2a 2b c 252a2bc25。第二种情况先取a , c a,ca,c的答案是2 a b 2 c 29 2a b 2c 292ab2c29。第三种情况先取b , c b,cb,c的答案是a 2 b 2 c 31 a 2b 2c 31a2b2c31。通过比较也可以发现第一种情况先取a , b a, ba,b是最优的。step 2: 证明推导到大范围也正确假设有n ( n 3 ) n(n 3)n(n3)堆果子合并完n − 3 n - 3n−3次之后还剩 3 堆果子可以用类似的方法证明取重量最小的两堆果子是最优的。因此取重量最小的两堆果子一定是最优的。代码实现选择priority_queue及使用方法现在需要一种数据结构能动态找到数据结构中最小值和次小值并删除他们再插入他们的和。我这里采用的是 stl 库中的priority_queue优先队列也被称为堆可以在O ( log ⁡ n ) O( \log n)O(logn)的时间复杂度内插入、查询优先队列中最大 / 最小值、删除优先队列中最大 / 最小值。priority_queue的使用方法如下。//定义方法#includequeue//需要的头文件priority_queueintq1;//定义一个大根堆查询和插入的是最大值priority_queueint,vectorint,greaterintq1;//定义一个小根堆查询和插入的是最小值//使用方法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_queueint,vectorint,greaterintq;//1.定义小根堆//2.将每堆果子的重量放进优先队列//我在这里不放了请读者自行思考longlongsum0;while(q.size()1){//4.重复步骤三直到只有一堆果子。inta1q.top();q.pop();inta2q.top();q.pop();//取出a1和a2即最小值和次小值suma1a2;//统计答案q.push(a1a2);//放入他们的和}