Skip to content

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

3
8
5
8

Sample Output

34

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;
}