P1090 [NOI洛谷P2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

可以用堆来实现，或者更简单一点的优先队列

优先队列：

#include<queue>
priority_queue<int,vector<int>,greater<int> > q;

因为每次合并后，最小的两个值都会更新，所以可以很好的利用优先队列内元素有序的特点，减少因反复排序带来的时间复杂度；

一开始我用STL自带的排序sort，报了5个TLE，后来意识到sort的实现主要依赖于快速排序，而每次合并后，真正需要排序的元素只有一个，快速排序有点大材小用，所以这可能是爆时限的原因，但后来也没有尝试自己实现一个排序算法，改用优先队列实现，直接AC，很好的利用了优先队列中元素有序的特点。

下面是代码实现：

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<fstream>
using namespace std;
bool compare(long long int x,long long int y) {
	return x < y ? true : false;
}
long long int n, s, i, sum;
int element;

vector<long long int> ans;
priority_queue<long long int, vector<long long int>, greater<long long int> >q;
int main(void) {
	cin >> n;
	ans.reserve(n);
	for (i = 0; i < n; i++) {
		cin >> element;
		q.emplace(element);
	}
	while (q.size()!=1) {
		sum = q.top();
		q.pop();
		sum += q.top();//因为优先队列无法访问指定下标元素，所以我选择先加一个，再删掉后再加上去
		ans.push_back(sum);//然后将答案存入数组中，作为一次合并数据
		q.pop();
		q.emplace(sum);//随后直接插入合并后的数据，利用优先队列的特点，再次排序
	}
	for (int i = 0; i < n - 1; i++) {
		s += ans[i];
	}
	cout << s;
	return 0;
}