合并果子

首先我们肯定知道，要想体力最小，那么一定要可重量小的先合并，因此我们肯定要对重量进行排序。那么我们是不是一直要保持这样一个有序的呢？

是的，但是我们合并出新的果子之后，是直接插入原序列中吗？显然太复杂，因此我们想到了用另外一个容器保存。现在我们解决的基本问题，接着是怎么存储。我们知道要使用最小的，所以我们想到了可以在一端出来，另一端进入的数据结构——队列。

q1存储原来的序列，q2存储合并后的果子，合并后的果子重量大体有两种情况：

1.这堆果子必然再次合并

2.这堆果子下次不会合并

所以我们还需要判断合并时使用的是哪个队列中的，然后将新合并的放入q2中

(排序可以直接sort,但是我想练习练习快排)

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
int a[N];
queue<int>q1,q2;
void quick_sort(int l,int r)
{
	if(l>=r)return;
    int i=l,j=r,x=a[l+r>>1];
    while(i<=j)
    {
    	while(x>a[i])i++;
        while(x<a[j])j--;
        if(i<=j)
        {
        	swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    quick_sort(l,j);
    quick_sort(i,r);
}
int main()
{
	int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    quick_sort(1,n);
    for(int i=1;i<=n;i++)
    {
    	q1.push(a[i]);
    }
    int ans=0;
    for(int i=1;i<n;i++)//合并n个果子只会合并n-1次
    {
    	int s[3];//因为要选出来2个最小的,所以开了2个空间,但是因为下标舒服,所以取的3
        for(int j=1;j<3;j++)
        {
        	if(q2.empty()||(!q1.empty()&&q1.front()<q2.front()))//q2为空表明现在还未合并
            {
            	s[j]=q1.front();
                q1.pop();
            }
            else
            {
            	s[j]=q2.front();
                q2.pop();
            }
        }
        ans+=s[1]+s[2];//合并果子消耗的体力加入
        q2.push(s[1]+s[2]);//将新合成的果子放入q2中进行下次判断
    }
    cout<<ans;
    return 0;
}