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

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

测试用例：

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

合并果子贪心算法实现：

#include <stdio.h>
#include <stdlib.h>

// 构造小根堆
void build_heap(int *arr, int len) {
    for (int i = len / 2; i >= 1; i--) {
        int k = i, j = k * 2;
        while (j <= len) {
            if (j < len && arr[j] > arr[j + 1]) {
                j++;
            }
            if (arr[k] > arr[j]) {
                int temp = arr[k];
                arr[k] = arr[j];
                arr[j] = temp;
                k = j;
                j = k * 2;
            } else {
                break;
            }
        }
    }
}

// 合并果子
int merge_fruits(int *fruits, int len) {
    int cost = 0;
    build_heap(fruits, len);
    while (len > 1) {
        int a = fruits[1];
        int b = fruits[2];
        int sum = a + b;
        cost += sum;
        fruits[1] = sum;
        fruits[2] = fruits[len--];
        build_heap(fruits, len);
    }
    return cost;
}

int main() {
    int fruits[] = {3, 4, 6};
    int len = sizeof(fruits) / sizeof(int);
    int cost = merge_fruits(fruits, len);
    printf("最小代价为：%d", cost);
    return 0;
}

该算法的时间复杂度为 O(nlogn)，其中 n 表示果子的个数。