https://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【输入文件】
输入文件fruit.in包括两行，第一行是一个整数n（1 <= n <= 10000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。
【输出文件】
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【样例输入】
3
1 2 9
【样例输出】
15
【数据规模】
对于30%的数据，保证有n <= 1000；
对于50%的数据，保证有n <= 5000；
对于全部的数据，保证有n <= 10000。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【输入文件】
输入文件fruit.in包括两行，第一行是一个整数n（1 <= n <= 10000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。
【输出文件】
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【样例输入】
3
1 2 9
【样例输出】
15
【数据规模】
对于30%的数据，保证有n <= 1000；
对于50%的数据，保证有n <= 5000；
对于全部的数据，保证有n <= 10000。
这个题目非常的经典，发放也很多，可以采用快排或者堆，其思想都是选取当前最小的两个堆进行合并。复杂度均为O(nlogn)，如果用有序队列维护，时间复杂度为O（n）。
每次选取进行合并的两堆，不是最先给定的堆，就是合并最初堆若干次后得到的新堆，所以需要维护两个单调递增队列，一个队列存最初给定的堆的值（1），一个存合并后得到的新值（2）。
每次选择时有三种状态：
1.选取队一的队首两个
2.选取队2的的队首两个
3.选取二者队首各一个
只需对每个队列的指针做相应的更改。
特别注意初始化。
这道题很好的运用了题目中决策的单调性，对初始对经行排序，保证了其单调性。而对于新产生的堆来说，一旦有新元素加入其中，则新元素一定大于原有元素。（很显然，由于队列1的单调性）。
也就是说，队列的单调性是自然而然的。是不需要维护的。要善于观察分析，才能发现。
X.
这个题目大家很熟悉的方法是进行排序后用堆进行操作，实现哈夫曼树，两步操作复杂度为O(nlogn)。自然这里的排序和上面一样，都是将数据映射到数轴上，再进行贪心处理。不过我在这里要进行一下扩展，利用一下单调性。原算法中堆的每次操作级别为logn，原因是每次的操作破坏了数据的单调性。如果我们把每次新合并出来的数据另外处理，保持原来数据的单调性，就减少了操作，降低了复杂度。具体方法是利用队列的性质，开两个数组，第一个数组存排序后的原数据，另一个数组存每次合成的数据，因为原数据是从小到大排布，新数组中的数据也会由小到大排布，这样，每次只要在这两个队列的开头选两次最小的元素再进行合并，并将生成的数据放入第二个队列的末端就可以了。这样的处理方式将合并过程的复杂度变成了O(n)
对于此类的如果生成的数，破坏了原来的单调性，则可以另外以开队列的方式解决，就是单调队列的问题
其实这题做法有很多。可以O（n^3）动规，可以O（n^2*logn）贪心，也可以用堆优化使得贪心的复杂度降到O（n*logn）。
但其实还有一种O（n）的合并方法——单调队列。
我们维护两个队列q1,q2，其中q1表示原本的那些堆（初始按升序排序），每次新合成的果子加入q2队尾。因为新合成的堆是越来越大的，所以q2也是有序的。那么我们很容易就可以从q1和q2中选出最小的两堆进行合并。
但是一开始题目给你的序列显然不是有序的对吧。如果用快排的话总复杂度就是O（n*logn+n），还不如堆优化。那么我们考虑桶排序，就可以把复杂度降为O（n+S）。
inline int read() {
int k = 0 , f = 1 ; char c = getchar() ;
for( ; !isdigit(c) ; c = getchar())
if(c == '-') f = -1 ;
for( ; isdigit(c) ; c = getchar())
k = k*10 + c-'0' ;
return k*f ;
}
int n ; int num[M+10], hh[N] ;
deque<int>q1 ;
deque<int>q2 ;
int main() {
n = read() ;
int x, y, ans = 0, mx = -INF ;
memset(num,0,sizeof(num)) ;
for(int i=1;i<=n;i++) {
x = read() ;
num[x]++ ;
mx = mx > x ? mx : x ;
}
for(int i=1;i<=mx;i++) {
while(num[i]) {
q1.push_back(i) ; num[i] -- ;
}
}
for(int i=1;i<n;i++) {
if(!q2.size()) x = q1.front(), q1.pop_front() ;
else if(!q1.size()) x = q2.front(), q2.pop_front() ;
else {
if(q1.front() < q2.front()) {
x = q1.front(), q1.pop_front() ;
} else x = q2.front(), q2.pop_front() ;
}
if(!q2.size()) y = q1.front(), q1.pop_front() ;
else if(!q1.size()) y = q2.front(), q2.pop_front() ;
else {
if(q1.front() < q2.front()) {
y = q1.front(), q1.pop_front() ;
} else y = q2.front(), q2.pop_front() ;
}
ans += (x+y) ;
q2.push_back(x+y) ;
}
printf("%d",ans) ;
return 0 ;
}
从这个问题可以深挖出神奇的哈夫曼树问题。
因为这题里合并的是二叉树，所以结点数量什么的都不用考虑。用堆维护数据，每次贪心取两个最小的合并即可（因为要使大数被累加的次数尽量少）
10 priority_queue <long long,vector<long long>,greater<long long> >q; 11 LL ans; 12 int n; 13 int main(){ 14 scanf("%d",&n); 15 int i,j; 16 LL x; 17 for(i=1;i<=n;i++){ 18 scanf("%lld",&x); 19 q.push(x); 20 } 21 for(i=1;i<n;i++){ 22 LL tmp=q.top();q.pop(); 23 tmp+=q.top();q.pop(); 24 q.push(tmp); 25 ans+=tmp; 26 } 27 printf("%lld\n",ans); 28 return 0; 29 }
