题意及思路

  • 题意：合并n种果子，每一次合并两堆，合并所需体力为果子的数量。问最小需要消耗多少体力？
  • 思路：😉题意简单明了，可以每次选取剩下堆中，最小数量的两堆，即😃贪心做法。😏很简单的吧。具体实现见代码。下述代码1中， 
priority_queue
为优先队列😄，下述代码1形式，自动将数据从小到大排序。最后，附上解法链接，戳下方链接。😉此外，我自己手写了一种类似于优先队列的代码。我的想法是，每次取完两个最小值后，🙂将他们的和插入到后面的位置上，便可以使得未合并的堆数值🙄整体有序。下述代码2中的arrange（）实现了此功能。
  • 收货：这题学到了c++的优先队列的概念，格式是 priority_queue<数据类型，存储容器类型， 优先的判定方式>。😆竞赛中c++还是比较友好的。

代码1 

// luogu-judger-enable-o2
#include<bits/stdc++.h>

using namespace std;

int n,x,ans;
priority_queue<int,vector<int>,greater<int> >q; //优先队列 

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
    	cin >> x;
    	q.push(x);
	}
	while(q.size()>=2){
		int a = q.top();
		q.pop();
		int b = q.top();
		q.pop();
		ans += a+b;
		q.push(a+b);
	}
	cout << ans << endl;
    
	return 0;
}

代码2 

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4+5;
int n,ans = 0,q[N];

void arrange(int id){
	for(int i=id+1;i<=n;i++){
		if(q[i]>=q[id]) break;
		swap(q[i],q[id]);
		id = i;
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
    	cin >> q[i];
	}
	sort(q+1,q+1+n);
	
	for(int i=2;i<=n;i++){
		ans += q[i-1]+q[i];
		q[i] = q[i-1]+q[i];
		arrange(i);
	}
    cout << ans << endl; 
    
	return 0;
}