#define PARENT(i) i/2
#define LEFT(i) 2*i
#define RIGHT(i) 2*i+1

class Solution {
public:
    void MaxHeapify(vector<int>& A, int i) {
        int heapSize = A[0];
        int l = LEFT(i), r = RIGHT(i);
        int largest;
        if (l <= heapSize && A[l] > A[i])
            largest = l;
        else largest = i;
        if (r <= heapSize && A[r] > A[largest])
            largest = r;
        if (largest != i) {
            swap<int>(A[i], A[largest]);
            MaxHeapify(A, largest);
        }
    }

    // 通过自底向上的方法嫁给你一个大小为 A[0]+1 的A数组转换为最大堆
    // 数组的有效长度为A[0], 有效数据由A[1]~A[1+A[0]]
    void BuildMaxHeap(vector<int>& A) {
        for (int i = A[0] / 2; i > 0; i--) 
            MaxHeapify(A, i);
    }

    int minStoneSum(vector<int>& piles, int k) {
        int len = piles.size();
        piles.push_back(len);
        swap(piles[0], piles[len]);
        len++;
        BuildMaxHeap(piles);
        for (int i = 0; i < k; i++) {
            piles[1] -= piles[1] / 2;
            MaxHeapify(piles, 1);
        }
        int ret = 0;
        for (int i = 1; i < len; i++) {
            ret += piles[i];
        };
        return ret;
    }
};