M18164: 剪绳子

Heap, http://cs101.openjudge.cn/pctbook/M18164/

小张要将一根长度为L的绳子剪成N段。准备剪的绳子的长度为L1,L2,L3...,LN，未剪的绳子长度恰好为剪后所有绳子长度的和。

每次剪断绳子时，需要的开销是此段绳子的长度。

比如，长度为10的绳子要剪成长度为2,3,5的三段绳子。长度为10的绳子切成5和5的两段绳子时，开销为10。再将5切成长度为2和3的绳子，开销为5。因此总开销为15。

请按照目标要求将绳子剪完最小的开销时多少。

已知，1<=N <= 20000，0<=Li<= 50000

输入

第一行：N，将绳子剪成的段数。 第二行：准备剪成的各段绳子的长度。

输出

最小开销

样例输入

3
2 3 5

样例输出

15

提示

tags: greedy, huffman

来源

cs101-2017 期末机考备选

#include <iostream>
#include <queue>
#include <functional>
#include <vector>
using namespace std;

long min_Heap(long arr[], long n)
{
    priority_queue<long, vector<long>, greater<long> > minHeap;
    for (int i = 0; i < n; i++)
    {
        // if (arr[i] != 0)
            // minHeap.push(arr[i]);
        minHeap.push(arr[i]);
    }
    long totalCost = 0;
    while (minHeap.size() > 1)
    {
        long first = minHeap.top();
        minHeap.pop();
        long second = minHeap.top();
        minHeap.pop();
        totalCost += first + second;
        minHeap.push(first + second);
    }
    return totalCost;
}

int main()
{
    int n;
    long arr[20001];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%ld", &arr[i]);
    }
    printf("%ld\n", min_Heap(arr, n));
    return 0;
}