Skip to content

14012: 【原4012】合并果子

题目

题目描述

author: noip2004 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4012

Description

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

Input Format

一共两行: 第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。 第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。

Output Format

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^31。

Sample Input

3 
1 2 9

Sample Output

15

数据范围

对于30％的数据，保证有n<=1000： 对于50％的数据，保证有n<=5000； 对于全部的数据，保证有n<=10000。

Limits

时间限制：1000ms

BugenZhao's solution 

//
// Created by BugenZhao on 2019/5/8.
//

//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BPRIORITYQUEUE_H
#define SBL_BPRIORITYQUEUE_H

namespace bpq {
    template<typename Item>
    struct greater {
        bool operator()(const Item &a, const Item &b) {
            return a > b;
        }
    };

    template<typename Item>
    struct less {
        bool operator()(const Item &a, const Item &b) {
            return a < b;
        }
    };
}


template<typename Item, typename Comparator = bpq::greater<Item>>
class BPriorityQueue {
    Comparator comparator;
    Item *pq;
    int N = 0;
    int maxN;
    int minN;

private:
    bool cmp(int i, int j) {
        return comparator(pq[i], pq[j]);
    }

    void exch(int i, int j) {
        Item item = pq[i];
        pq[i] = pq[j];
        pq[j] = item;
    }

    void resize(int newMaxN) {
        Item *old = pq;
        pq = new Item[newMaxN + 1];
        int length = newMaxN > maxN ? maxN : newMaxN;
        for (int i = 1; i <= length; ++i) {
            pq[i] = old[i];
        }
        delete[] old;
    }

    void swim(int k) {
        while (k > 1 && cmp(k, k / 2)) {
            exch(k / 2, k);
            k /= 2;
        }
    }

    void sink(int k) {
        int j;
        while (2 * k <= N) {
            j = 2 * k;
            j += (j < N && cmp(j + 1, j));
            if (cmp(j, k)) {
                exch(k, j);
                k = j;
            } else break;
        }
    }


public:
    BPriorityQueue() {
        this->maxN = 1;
        this->minN = -1;
        pq = new Item[1 + 1];
    }

    BPriorityQueue(int maxN) {
        this->maxN = maxN;
        this->minN = maxN;
        pq = new Item[maxN + 1];
    }

    BPriorityQueue(const Item *pq, int size) {
        maxN = N = size;
        minN = N;
        this->pq = new Item[size + 1];
        for (int i = 1; i <= N; ++i) {
            this->pq[i] = pq[i - 1];
        }
        for (int k = N / 2; k >= 1; --k) {
            sink(k);
        }
    }

    bool isEmpty() {
        return N == 0;
    }

    int size() {
        return N;
    }

    void insert(const Item &item) {
        if (N == maxN)
            resize(2 * N);
        pq[++N] = item;
        swim(N);
    }

    Item pop() {
        if (N <= maxN / 4) {
            if (maxN / 2 >= minN) resize(maxN / 2);
            else resize(minN);
        }
        Item item = pq[1];
        exch(1, N);
        --N;
        sink(1);
        return item;
    }

    const Item &peek() {
        return pq[1];
    }

    virtual ~BPriorityQueue() {
        delete[] pq;
    }
};


#endif //SBL_BPRIORITYQUEUE_H


#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int tmp;
    BPriorityQueue<int, bpq::less<int>> pq(n);
    for (int i = 0; i < n; ++i) {
        cin >> tmp;
        pq.insert(tmp);
    }

    int a, b;
    int ans = 0;
    while (pq.size() >= 2) {
        a = pq.pop();
        b = pq.pop();
        pq.insert(a + b);
        ans += a + b;
    }

    cout << ans << endl;
    return 0;
}

ligongzzz's solution 

#include "iostream"
using namespace std;

template <class T>
class mVector {
    T** vector_data = nullptr;
    unsigned int size = 0;
    unsigned int capacity = 0;

public:
    //构造函数
    mVector() = default;
    mVector(unsigned int _size) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
    }
    mVector(unsigned int _size, const T& val) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
        for (unsigned int i = 0; i < _size; ++i)
            vector_data[i] = new T(val);
    }
    mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
        vector_data = new T * [capacity] {nullptr};
        for (int i = 0; i < size; ++i)
            vector_data[i] = new T(*_vector.vector_data[i]);
    }
    //析构函数
    ~mVector() {
        for (unsigned int i = 0; i < size; ++i)
            delete vector_data[i];
        delete[] vector_data;
    }

    //迭代器
    class iterator {
        T** pos = nullptr;
        friend iterator mVector<T>::begin();
        friend iterator mVector<T>::end();
        friend void mVector<T>::erase(const iterator& val);
    public:
        iterator() = default;
        iterator(const iterator& other) {
            pos = other.pos;
        }
        iterator& operator++() {
            ++pos;
            return *this;
        }
        iterator operator++(int) {
            iterator temp(*this);
            ++pos;
            return temp;
        }
        iterator& operator--() {
            --pos;
            return *this;
        }
        iterator operator--(int) {
            iterator temp(*this);
            --pos;
            return temp;
        }
        bool operator==(const iterator& other) const {
            return pos == other.pos;
        }
        bool operator!=(const iterator& other) const {
            return pos != other.pos;
        }
        iterator& operator=(const iterator& other) {
            pos = other.pos;
            return *this;
        }
        T& operator*() const {
            return **pos;
        }
    };

    //增加元素
    void push_back(const T & val) {
        if (size < capacity)
            vector_data[size++] = new T(val);
        else {
            T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
            for (unsigned int i = 0; i < size; ++i)
                temp_data[i] = vector_data[i];
            temp_data[size++] = new T(val);
            capacity = (capacity + 1) * 2;
            delete[] vector_data;
            vector_data = temp_data;
        }
    }

    //删除末尾
    void pop_back() {
        delete vector_data[size];
        vector_data[size--] = nullptr;
    }

    //清空
    void clear() {
        for (unsigned int i = 0; i < size; ++i) {
            delete vector_data[i];
            vector_data[i] = nullptr;
        }
        size = 0;
    }

    //删除
    void erase(const iterator & val) {
        delete* val.pos;
        for (auto p = val.pos; p != vector_data + size - 1; ++p)
            * p = *(p + 1);
        --size;
        vector_data[size] = nullptr;
    }

    //重载运算符
    T & operator[](const unsigned int& pos) {
        return *vector_data[pos];
    }

    iterator begin() {
        iterator temp;
        temp.pos = vector_data;
        return temp;
    }

    iterator end() {
        iterator temp;
        temp.pos = vector_data + size;
        return temp;
    }

};

template <class T>
class myPriorityQueue {
public:
    mVector<T> queueData;
    unsigned int sizeOfQueue = 0;
    bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

    //向下过滤
    void percolateDown(unsigned int pos) {
        while (pos * 2 <= sizeOfQueue) {
            if (pos * 2 + 1 > sizeOfQueue) {
                //交换
                if (cmp(queueData[pos * 2], queueData[pos])) {
                    auto temp = queueData[pos * 2];
                    queueData[pos * 2] = queueData[pos];
                    queueData[pos] = temp;
                }
                break;
            }
            else {
                bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
                if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
                    auto temp = queueData[pos * 2 + minNum];
                    queueData[pos * 2 + minNum] = queueData[pos];
                    queueData[pos] = temp;
                    pos = pos * 2 + minNum;
                }
                else break;
            }
        }
    }


    //构建
    myPriorityQueue() {
        queueData.clear();
        queueData.push_back((T)0);
        sizeOfQueue = 0;
    }

    //compare函数返回父结点a与孩子结点b的关系正确与否
    myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
        queueData.clear();
        queueData.push_back(*new T);
        sizeOfQueue = 0;
    }

    //根据数组建立堆
    void buildHeap(T* eleData, unsigned int eleNum) {
        queueData.clear();
        sizeOfQueue = eleNum;
        queueData.push_back(*new T);
        for (unsigned int i = 1; i <= eleNum; i++)
            queueData.push_back(eleData[i - 1]);
        //向下过滤
        for (unsigned int pos = eleNum / 2; pos > 0; pos--)
            percolateDown(pos);
    }

    void refresh() {
        //向下过滤
        for (unsigned int pos = size() / 2; pos > 0; pos--)
            percolateDown(pos);
    }

    //判断是否空
    bool empty() {
        return sizeOfQueue == 0;
    }

    //返回队列大小
    auto size() {
        return sizeOfQueue;
    }

    //入队
    void push(const T & input) {
        sizeOfQueue++;
        queueData.push_back(input);

        //向上过滤
        for (auto i = sizeOfQueue; i > 1; i = i / 2) {
            //判断是否比父结点更小
            if (cmp(queueData[i], queueData[i / 2])) {
                //交换
                auto temp = queueData[i];
                queueData[i] = queueData[i / 2];
                queueData[i / 2] = temp;
            }
            else break;
        }
    }

    //队列最前
    T top() {
        return queueData[1];
    }

    //出队
    T pop() {
        auto temp = queueData[1];
        queueData[1] = queueData[sizeOfQueue--];
        queueData.pop_back();
        percolateDown(1);
        return temp;
    }
};

int weight[20000] = { 0 };

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> weight[i];

    //排除特殊情况
    if (n == 1) {
        cout << weight[0];
        return 0;
    }

    myPriorityQueue<int> fruit;
    fruit.buildHeap(weight, n);

    long long ans=0;
    //不断循环
    while (fruit.sizeOfQueue > 2) {
        if (fruit.queueData[2] <= fruit.queueData[3]) {
            fruit.queueData[2] += fruit.queueData[1];
            ans += fruit.queueData[2];
            fruit.percolateDown(2);
        }
        else {
            fruit.queueData[3] += fruit.queueData[1];
            ans += fruit.queueData[3];
            fruit.percolateDown(3);
        }
        //剔除最小的元素
        fruit.pop();
    }
    ans += fruit.queueData[1] + fruit.queueData[2];
    cout << ans;
    return 0;
}

Neight99's solution 

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

template <class Type>
class priorityQueue {
   private:
    int currentSize;
    Type *array;
    int maxSize;

    void doubleSpace();
    // void buildHeap();
    void percolateDown(int);

   public:
    priorityQueue(int capacity = maxN);
    // priorityQueue(const Type data[],int size);
    ~priorityQueue();
    bool isEmpty() const;
    void enQueue(const Type &x);
    Type deQueue();
    Type getHead() const;
};

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

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) {
        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 minItem;

    minItem = array[1];
    array[1] = array[currentSize--];
    percolateDown(1);

    return minItem;
}

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

        if (array[child] < tmp) {
            array[hole] = array[child];
        } else {
            break;
        }
    }
    array[hole] = tmp;
}

template <class Type>
void priorityQueue<Type>::doubleSpace() {
    Type *tmp = array;

    maxSize *= 2;

    array = new Type[maxSize];
    for (int i = 0; i < currentSize; i++) {
        array[i] = tmp[i];
    }

    delete[] tmp;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, tmp1, tmp2, tmp3;
    long long strength = 0;
    priorityQueue<int> fruits;

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> tmp1;
        fruits.enQueue(tmp1);
    }

    for (int i = 0; i < N - 1; i++) {
        tmp1 = fruits.deQueue();
        tmp2 = fruits.deQueue();
        tmp3 = tmp1 + tmp2;
        fruits.enQueue(tmp3);
        strength += tmp3;
    }

    cout << strength;
}

q4x3's solution 

/**
 * 最小堆 + 哈夫曼
 * 每次把最小的两个取出来加到一起
 * 加入ans
 * 并放回堆中
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

long long int N, F[10233], ans;

void down(long long int rt, long long int size) {
    long long int tmp = F[rt];
    if((rt << 1) > size) return;
    else if((rt << 1 | 1) > size) {
        if(tmp > F[rt << 1]) {
            F[rt] = F[rt << 1];
            F[rt << 1] = tmp;
        }
        return;
    } else {
        long long int chi1 = F[rt << 1], chi2 = F[rt << 1 | 1];
        if(chi1 < tmp && chi1 <= chi2) {
            F[rt] = chi1;
            F[rt << 1] = tmp;
            down(rt << 1, size);
        } else if(chi2 < tmp && chi2 <= chi1) {
            F[rt] = chi2;
            F[rt << 1 | 1] = tmp;
            down(rt << 1 | 1, size);
        }
    }
}

void build() {
    for(long long int i = N / 2;i > 0;-- i) {
        down(i, N);
    }
}

void op(long long int size) {
    long long int head = F[1];
    F[1] = F[size];
    down(1, size - 1);
    F[1] += head; ans += F[1];
    down(1, size - 1);
}

int main() {
    scanf("%lld", &N);
    for(long long int i = 1;i <= N;++ i)
        scanf("%lld", &F[i]);
    build();
    for(long long int i = 0;i < N - 1;++ i) {
        op(N - i);
    }
    cout << ans << endl;
    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;

#include <stdio.h>

template<typename T>
struct Heap {
    T *data;
    int cap, len;

    Heap(int cap = 1024) : cap(cap + 1), len(0) {
        data = new T[cap];
    }

    Heap(const Heap& that) : cap(that.cap), len(that.len) {
        data = new T[cap];
        memcpy(data, that.data, sizeof(T) * cap);
    }

    ~Heap() { delete[] data; }

    void push(const T &x) {
        data[++len] = x;
        swim(len);
    }

    T pop() {
        swap(data[1], data[len--]);
        sink(1);
        return data[len + 1];
    }

    void top() {
        return data[1];
    }

    bool less(int a, int b) {
        if (a > len || b > len) return false;
        return data[a] < data[b];
    }

    void swim(int idx) {
        int _idx;
        while (idx > 1 && less(idx, _idx = idx / 2)) {
            swap(data[idx], data[_idx]);
            idx = _idx;
        }
    }

    void sink(int idx) {
        int _idx;
        while ((_idx = 2 * idx) <= len) {
            if (_idx < len && less(_idx + 1, _idx)) _idx++;
            if (less(idx, _idx)) break;
            swap(data[idx], data[_idx]);
            idx = _idx;
        }
    }

    bool empty() {
        return len == 0;
    }
};

int main() {
    int n;
    int x[20000];
    long long sum = 0;
    Heap <int> heap(20000);
    cin >> n;
    int _data;
    for (int i = 0; i < n; i++) {
        cin >> _data;
        heap.push(_data);
    }
    for (int i = 0; i < n - 1; i++) {
        int op1 = heap.pop(), op2 = heap.pop();
        int s = op1 + op2;
        heap.push(s);
        sum += s;
    }
    cout << sum << endl;
    return 0;
}

victrid's solution 

#include <iostream>
using namespace std;
long long strage[400005];
int treesize;
void swap(long long& a1, long long& a2) {
    if (a1 != a2) {
        a1 ^= a2;
        a2 ^= a1;
        a1 ^= a2;
    }
    return;
};
void insert(long long i) {
    strage[++treesize] = i;
    int x              = treesize;
    while (x != 1) {
        if (strage[x] < strage[x >> 1]) {
            swap(strage[x], strage[x >> 1]);
            x >>= 1;
        } else
            break;
    }
    return;
}
long long pop() {
    swap(strage[1], strage[treesize]);
    treesize--;
    int i = 2;
    while (i <= treesize) {
        if ((i | 1) <= treesize && strage[i | 1] < strage[i])
            i |= 1;
        if (strage[i] < strage[i >> 1]) {
            swap(strage[i], strage[i >> 1]);
            i <<= 1;
        } else
            break;
    }
    return strage[treesize + 1];
}
int main() {
    int n, x, y;
    long long ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        insert(x);
    }
    while (treesize > 1) {
        x = pop();
        y = pop();
        ans += x + y;
        insert(x + y);
    }
    printf("%lld", ans);
    return 0;
}

WashSwang's solution 

#include <iostream>
#include <cstdio>
using namespace std;
int rmargin,lmargin,dmargin,m,n,p,q,t,x,sx,sy,patx[1000001],paty[1000001],map[1001][1001],num,pnum;
bool flag;
int main() {
    scanf("%d",&t);
    for (int i=0;i<t;++i){
        flag=true;
        num=0;
        lmargin=0;
        rmargin=0;
        dmargin=0;
        pnum=0;
        scanf("%d%d%d%d",&m,&n,&p,&q);
        for (int j=0;j<m;++j)
            for (int k=0;k<n;++k) {
                scanf("%d", &map[j][k]);
                if (map[j][k]) pnum++;
            }
        for (int j=0;j<p;++j)
            for (int k=0;k<q;++k)
            {
               scanf("%d",&x);
               if (x){
                   if (num==0) {
                       sx=j;
                       sy=k;
                       num++;
                   }
                   else{
                       patx[num]=j-sx;
                       paty[num]=k-sy;
                       if (paty[num]<0)
                           lmargin=max(lmargin,paty[num]);
                       rmargin=max(rmargin,paty[num]);
                       dmargin=max(dmargin,patx[num]);
                       num++;
                   }
               }
            }
        for (int j=0;j<m-dmargin;++j){
            for (int k=lmargin;k<n-rmargin;++k)
                if (map[j][k]){
                    map[j][k]=0;
                    for (int l=1;l<num;++l)
                        if (!map[j+patx[l]][k+paty[l]]) {
                            flag = false;
                            break;
                        }
                        else
                            map[j+patx[l]][k+paty[l]]=0;
                    if (!flag) break;
                    pnum-=num;
                    if (!pnum) break;
                }
            if (!flag) break;
            if (!pnum) break;
        }
        if (!flag) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

yyong119's solution 

#include <iostream>
#include <queue>

using namespace std;
priority_queue <int, vector<int>, greater<int> > que;
long n, cost, temp;

int main() {

    cin>>n;
    for (int i = 0; i < n; i++) {
        cin>>temp;
        que.push(temp);
    }

    while (que.size() != 1) {
        temp = que.top(); que.pop();
        temp += que.top(); que.pop();
        cost +=temp; que.push(temp);
    }
    cout<<cost;
}