14288: 【原4288】牧场维修

题目描述

author: jianglin huang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4288

Description

农民杨想要维修牧场周围一段篱笆，他测量了篱笆并发现他需要N块小木条（1 <= N <= 20,000), 每块小木条的长度为整数Li（1 <= Li <= 50,000）。他需要购买一块足够长的的木条，这块木条的长度足够将其锯成所需的N块小木条（该长木条长度为N块小木条长度Li的和）。忽略锯断木条时，由于锯末带来的误差。

农民杨突然意识到，他没有锯子，于是农民杨拿着他购买的长木条，恳请地主黄借给他一把锯子。很不幸的是，万恶的地主黄是个吝啬的资本家，他不愿意免费借给农民杨锯子，只愿意以一定规则收取费用给农民杨使用，该规则是：在农民杨第i次锯木条时，将一段长为li的木条锯成li1和li2，那么第i次锯木条的收费为li1+li2，也就是说是被锯断的这块木条的长，而农民杨需要N块小木条，那么就需要锯N-1次，农民杨要给地主黄的费用就为这N-1次的费用总和。

地主黄让农民杨自己决定锯木条的顺序和位置。众人拾材火焰高，来帮农民杨想一想，怎么锯那根足够长的木条，使得他要付的钱最少又可以得到需要的N块小木条呢？

Input Format

第1行：整数N，小木条的块数第2..N+1行：每一行都是一个大于0的整数，表示所需小木条的长度

Output Format

第1行：一个整数，他必须花费的最少的钱

Sample Input

Sample Output

Hint

农民杨想把一块长为21（21=8+5+8）的木条锯成长度分别为8，5，8的小木条。第一次锯将长为21的木条锯成长分别为13和8的两块木条，花费为21；第二次锯将长为13的木条锯为8和5的小木条，花费为13，于是总的花费为34（34=21+13）。如果21被分成16和5，那么总的花费将是37（37=21+16），大于34。

Zsi-r's solution

#include <iostream>

using namespace std;

template <class Type>
class priorityQueue
{
public:
    priorityQueue(int capacity = 100);
    priorityQueue(const Type data[],int size);
    ~priorityQueue();
    bool isEmpty()const;
    void enQueue(const Type &x);
    Type deQueue();
    Type getHead() const;
    int currentSize;
private:

    Type *array;//array[0]不放东西
    int maxSize;

    void doubleSpace();
    void buildHeap();//对一串数字进行有序化建堆
    void percolateDown(int hole);
};

template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
{
    array = new Type[capacity];
    maxSize = capacity;
    currentSize = 0;
}

template <class Type>
priorityQueue<Type>::~priorityQueue()
{
    delete[] array;
}

template <class Type>
bool priorityQueue<Type>::isEmpty() const
{
    return currentSize == 0;
}

template <class Type>
Type priorityQueue<Type>::getHead() const
{
    return array[1];
}

template <class Type >
void priorityQueue<Type>::enQueue(const Type &x)
{
    if (currentSize == maxSize-1)//因为array[0]不放东西
        doubleSpace();

    //向上过滤
    int hole = ++currentSize;
    for (; hole > 1 && x <= array[hole / 2]; hole /= 2)
        array[hole] = array[hole / 2];
    array[hole] = x;
}

template <class Type >
Type priorityQueue<Type >::deQueue()
{
    Type miniItem;
    miniItem = array[1];
    array[1] = array[currentSize--];//把最大(maybe)的数放在第一个，再向下过滤
    percolateDown(1);
    return miniItem;
}

template<class Type >
void priorityQueue<Type >:: percolateDown(int hole)//向下过滤
{
    int child;
    Type tmp = array[hole];
    for (; hole * 2 <= currentSize; hole = child){
        child = hole * 2;
        if (child!=currentSize && array[child+1]<array[child])//找小的儿子，如果child==currentSize，则没有右儿子
            child++;
        if(array[child]<tmp)
            array[hole] = array[child];
        else
            break;
    }
    array[hole] = tmp;
}

template <class Type >
void priorityQueue<Type >::buildHeap()
{
    for (int i = currentSize / 2; i > 0;i--)
        percolateDown(i);
}

template <class Type>
priorityQueue<Type>::priorityQueue(const Type *items, int size) : maxSize(size + 10), currentSize(size)
{
    array = new Type[maxSize];
    for (int i = 0; i < size;i++)
        array[i + 1] = items[i];
    buildHeap();
}

template <class Type >
void priorityQueue<Type >::doubleSpace()
{
    Type *tmp = array;
    maxSize *= 2;
    array = new Type[maxSize];
    for (int i = 0; i <= currentSize; i++) //当currentSize == maxSize-1时，调用doubleSpace()
        array[i] = tmp[i];
    delete[] tmp;
}

int main()
{
    int num;
    int item;
    int sum = 0;
    cin >> num;
    priorityQueue<int> que(num*2);
    for (int i = 0; i < num;i++)
    {
        cin >> item;
        que.enQueue(item);
    }
    while (que.currentSize>1)
    {
        int temp1 = 0,temp2 = 0;
        temp1 = que.deQueue();
        temp2 = que.deQueue();
        sum += temp1;
        sum += temp2;
        que.enQueue(temp1 + temp2);
    }
    cout << sum;
}