c++合并果子测试用例,C++合并果子-贪心算法

非常感谢您的提问！以下是一个测试用例和 C++ 的合并果子贪心算法实现。

测试用例：

假设有三个果子，它们的大小分别是 3、4、6，合并果子的代价是两个果子大小之和，即若将大小分别为 a 和 b 的果子合并，则代价为 a+b。现在需要将这三个果子合并成一个，求最小代价。

合并果子贪心算法实现：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 合并果子
int merge_fruits(priority_queue<int, vector<int>, greater<int>> &fruits) {
    int cost = 0;
    while (fruits.size() > 1) {
        int a = fruits.top();
        fruits.pop();
        int b = fruits.top();
        fruits.pop();
        int sum = a + b;
        cost += sum;
        fruits.push(sum);
    }
    return cost;
}

int main() {
    priority_queue<int, vector<int>, greater<int>> fruits;
    fruits.push(3);
    fruits.push(4);
    fruits.push(6);
    int cost = merge_fruits(fruits);
    cout << "最小代价为：" << cost << endl;
    return 0;
}

该算法使用了 STL 中的 priority_queue 来实现小根堆，其时间复杂度为 O(nlogn)，其中 n 表示果子的个数。