合并果子 - 最小体力消耗算法详解

题目描述

果园里有 'n' 堆果子，第 'i' 堆果子有 'a_i' 个。每次你可以将 2 堆果子合并成 1 堆，合并后的果子堆里的果子个数为合并的所有果子个数之和，同时你要消耗合并的所有果子个数之和的体力。 你可以自由选择合并顺序，最终要将所有果子堆合并成 1 堆，求花费体力的最小值。

输入格式

从标准输入读入数据。 第一行输入一个正整数 'n'（'n'≤1000）。 第二行输入 'n' 个正整数 'a_i'（'a_i'≤1000）。

输出格式

输出到标准输出。 输出一个整数，表示花费体力的最小值。

样例 #1

样例输入 #1

5
2 3 1 4 5

样例输出 #1

33

提示

样例1解释

初始局面 (2,3,1,4,5)。

• 第 1 次合并 2 个果子的堆和 1 个果子的堆，消耗 3 点体力，局面变为 (3,4,5,3)；
• 第 2 次合并 3 个果子的堆和 3 个果子的堆，消耗 6 点体力，局面变为 (4,5,6)；
• 第 3 次合并 4 个果子的堆和 5 个果子的堆，消耗 9 点体力，局面变为 (6,9)；
• 第 4 次合并 6 个果子的堆和 9 个果子的堆，消耗 15 点体力，局面变为 (15)。 总共消耗 33 点体力。

算法思路

本题可以使用贪心算法来求解。每次选择两堆果子数量最小的进行合并，可以保证合并后的果子堆数量尽可能小，从而降低后续的体力消耗。

可以使用优先队列（小根堆）来维护所有果子堆的数量，每次取出两个最小的果子堆进行合并，并将合并后的果子堆数量重新放入优先队列。

C++ 代码实现

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,greater<int>>Q;//小根堆
    int n,m,x,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        Q.push(x);
    }
    while(Q.size()>1)
    {
        int a=Q.top();Q.pop();
        int b=Q.top();Q.pop();
        ans+=a+b;
        Q.push(a+b);
    }
    cout<<ans;
    return 0;
}

代码解释

1. 使用 priority_queue<int,vector<int>,greater<int>>Q 创建一个小根堆，用于维护所有果子堆的数量。
2. 输入果子堆的数量 'n' 和每个果子堆的果子数量 'a_i'，并将其放入优先队列。
3. 使用 while(Q.size()>1) 循环，当优先队列中还有两个及以上元素时，不断执行以下操作：
   • 使用 Q.top() 取出优先队列中最小元素 'a'，并使用 Q.pop() 从优先队列中删除该元素。
   • 使用 Q.top() 取出优先队列中最小元素 'b'，并使用 Q.pop() 从优先队列中删除该元素。
   • 计算合并 'a' 和 'b' 需要的体力消耗 ans+=a+b。
   • 将合并后的果子堆数量 a+b 重新放入优先队列中。
4. 最后输出 ans，即花费体力的最小值。

总结

本题通过贪心算法和优先队列的应用，可以高效地求解合并果子最小体力消耗的问题。代码简洁易懂，适合初学者学习。