/*起初想用最小堆实现,发现不如直接使用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; }
/*还存在法3,利用哈夫曼树,还未掌握,先暂留*/