合并果子

每次合并权值最小的两个点，要求最后总体体力值最小。
证明
1. 权值最小的两个点，深度最深，且可以互为兄弟。
2. 证明n - 1 个点合并的最小值一定满足 n 个点合并的最小值。证明 F(n) = F(n - 1) + (a + b) 其中 (a + b) 又是最小的两个点，证毕。

#include <isotream>
#include <algorithm>
#include <queue>

using namespace std;



int main()
{
    int n;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> heap;

    while (n --)
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);

    }
    printf("%d", res);
    return 0;

}

合并果子

FEATURED TAGS