题解 | #搬水果#

/*起初想用最小堆实现，发现不如直接使用vector来贪心地搬运水果。
以下为使用vector实现的法1：*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n=0;
    int fruit_num=0;//每种水果的数量
    int merge_fruit=0;
    int res=0;
    vector<int> fruits;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>fruit_num;
        fruits.push_back(fruit_num);
    }
    sort(fruits.begin(),fruits.end());
    while(fruits.size()!=1){
        merge_fruit=fruits[0]+fruits[1];//计算两堆水果和
        res+=merge_fruit;//消耗体力
        for(int i=0;i<2;i++){
            vector<int>::iterator it=fruits.begin();
            fruits.erase(it);//去除元素
        }
        fruits.push_back(merge_fruit);//合并后放入容器
        sort(fruits.begin(),fruits.end());//重新排序
    }
    cout<<res<<endl;
    return 0;
}

/*
使用优先队列实现小根堆，优先队列声明：priority_queue<Type,Container,Functional> que;
Type:为数据类型；
Container：为实现优先队列的底层容器；
Functional：为元素之间的比较方式。
第一个参数不可以省，后两个参数可省。默认为降序less（即大顶堆）。
升序greater（小顶堆）。
*/
#include <iostream>
#include <queue>
using namespace std;
int main(){
    //利用优先队列构造小顶堆
    priority_queue< int,vector<int>,greater<int> > min_heap;//数据类型，底层容器，比较方式
    int n=0;
    int fruit_num=0;
    int first=0,second=0;
    int res=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>fruit_num;
        min_heap.push(fruit_num);
    }
    while(min_heap.size()!=1){
        first=min_heap.top();
        min_heap.pop();
        second=min_heap.top();
        min_heap.pop();
        res+=(first+second);
        min_heap.push(first+second);
    }
    cout<<res<<endl;
    return 0;
}