TJUOJ 4441: 合并果子（堆）

补程设课，没什么事干，就在学校OJ上找了道简单题做
算法复健一下，顺便试一试代码块插入

题目给了提示，应该是道堆排序的题
由于每次体力增加值为当前已合并果子的总数，因此我们只需保证每次合并的两个堆都是当前果子数量最少的两个堆即可
思路有些像霍夫曼编码，但题目只要求求最终的体力消耗，所以没有构建霍夫曼树的必要
准备直接做一个最小堆，每次合并操作都取两次堆顶元素，将求出的和累加至totalCost变量中，并放回堆里
循环至只剩一个元素时，totalCost中值即是所求答案

理论存在，实践开始

Input && Init

首先进行数据读入和建堆操作
使用scanf读入数据增加速度
然后偷个懒，用 #include <algorithem> 的make_heap函数建堆
需要注意，题中给出的数据最大可能为n=30000，且每项均为20000
因此结果最大可能为2e4至6e8的等差求和，即9e12左右
考虑到我们会将中间结果存在堆中，因此需要一个64位的堆和totalCost

CODE

uint64_t *heap;
int N;
scanf("%d", &N);
heap = new uint64_t[N];

for(int i = 0; i < N; i++)
    scanf("%lld", heap + i);

make_heap(heap, heap + N, greater<>());

Main Algorithem

现在编写主算法
每次从堆顶取两个数进行加和，随后将结果存入堆中，并累加totalCost，直至堆中只剩一个元素

CODE

uint64_t totalCost = 0, currentCost;
for(int mergeTimes = N - 1; mergeTimes > 0; mergeTimes--) {
    currentCost = heap[0];
    heap[0] = heap[mergeTimes];
    maintainHeap(heap, mergeTimes);

    currentCost += heap[0];
    heap[0] = currentCost;
    maintainHeap(heap, mergeTimes);
    
    totalCost += currentCost;
}

Quoting Function

最后实现用于维护堆的maintainHeap函数
我们只需跟踪堆顶元素，并循环判断判断它和它最小孩子的大小关系，若大于则与之交换并继续循环，否则返回

CODE

//Find the minimum element in heap[i]'s children
//Return it's index
int findMinChild(uint64_t* heap, int parentIndex, int length) {
    if((parentIndex * 2) + 2 < length)
        return heap[(parentIndex * 2) + 1] < heap[(parentIndex * 2) + 2] ? (parentIndex * 2) + 1 : (parentIndex * 2) + 2;
    else if((parentIndex * 2) + 1 < length)
        return (parentIndex * 2) + 1;
    else
        return -1;
}

//maintain the heap as a minimum heap after changing the top
void maintainHeap(uint64_t* heap, int length) {
    int parentIndex = 0, minChildIndex;
    
    minChildIndex = findMinChild(heap, parentIndex, length);
    while (heap[parentIndex] > heap[minChildIndex] && minChildIndex != -1) {
        long long temp = heap[parentIndex];
        heap[parentIndex] = heap[minChildIndex];
        heap[minChildIndex] = temp;
        
        parentIndex = minChildIndex;
        minChildIndex = findMinChild(heap, parentIndex, length);
    }
}

至此编程结束，成功AC