30702：最小合并代价

题目

每次合并当前两堆最小的材料，合并代价是两堆重量之和，求合并为一堆的最小总代价。

解析

把所有重量放入最小堆。每轮取出最小的两项并放回它们的和。交换论证表明，在任意最优合并树中，两棵最浅的子树可以安排为最底层兄弟；把它们替换成最小的两堆不会增加代价，递归应用即可得到贪心选择。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

static void swap_u64(uint64_t *left, uint64_t *right) {
    uint64_t temporary = *left;
    *left = *right;
    *right = temporary;
}

static void sift_down(uint64_t *heap, size_t size, size_t index) {
    for (;;) {
        size_t smallest = index;
        if (index < size / 2) {
            size_t left = index * 2 + 1;
            size_t right = left + 1;
            if (heap[left] < heap[smallest]) {
                smallest = left;
            }
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }
        }
        if (smallest == index) {
            return;
        }
        swap_u64(&heap[index], &heap[smallest]);
        index = smallest;
    }
}

static uint64_t pop_min(uint64_t *heap, size_t *size) {
    uint64_t result = heap[0];
    --*size;
    if (*size > 0) {
        heap[0] = heap[*size];
        sift_down(heap, *size, 0);
    }
    return result;
}

static void push_min(uint64_t *heap, size_t *size, uint64_t value) {
    size_t index = (*size)++;
    heap[index] = value;
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (heap[parent] <= heap[index]) {
            break;
        }
        swap_u64(&heap[parent], &heap[index]);
        index = parent;
    }
}

bool minimum_merge_cost(
    const uint64_t *weights,
    size_t count,
    uint64_t *out_cost
) {
    if (out_cost == NULL || (count > 0 && weights == NULL)) {
        return false;
    }
    if (count <= 1) {
        *out_cost = 0;
        return true;
    }
    if (count > SIZE_MAX / sizeof(uint64_t)) {
        return false;
    }
    uint64_t *heap = malloc(count * sizeof *heap);
    if (heap == NULL) {
        return false;
    }
    for (size_t i = 0; i < count; ++i) {
        heap[i] = weights[i];
    }
    for (size_t i = count / 2; i > 0; --i) {
        sift_down(heap, count, i - 1);
    }

    size_t heap_size = count;
    uint64_t total = 0;
    while (heap_size > 1) {
        uint64_t first = pop_min(heap, &heap_size);
        uint64_t second = pop_min(heap, &heap_size);
        if (first > UINT64_MAX - second) {
            free(heap);
            return false;
        }
        uint64_t merged = first + second;
        if (total > UINT64_MAX - merged) {
            free(heap);
            return false;
        }
        total += merged;
        push_min(heap, &heap_size, merged);
    }
    free(heap);
    *out_cost = total;
    return true;
}

建堆为 $O(n)$，每次合并执行两次弹出和一次插入，整体时间复杂度为 $O(n\log n)$，额外空间为 $O(n)$。