题解 | #智乃的果子#

使用优先队列，可以快速取出重量最小的果堆以使用。

本题需要从重量最小的果堆开始选取，若该重量的果堆个数为单数，则让多余的那个果堆与重量第二小的果堆合并；若该重量的果堆个数为复数，则自己内部消化。

下面是代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> st;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int c,w;
		cin>>c>>w;
		st.push({w,c});
	}
	int f=0,pre=0,ans=0;//f判断上轮合并后是否存在多余的1个果堆,pre为多余的那个果堆的重量
	while(!st.empty()){
		pair<int,int>x=st.top();//取个体重量最小的果堆
		st.pop();
		int q=0,cnt=x.second;//q为合并后的重量,cnt为果堆的个数
		if(f!=0)//上轮合并后存在多余1个果堆
		{
			cnt--;//从果堆x中取出一个,与多余果堆合并
			q=pre+x.first;
			ans+=q;
			st.push({q,1});
			f=0;//多余果堆已被合并,不存在多余果堆了
		}
		if(f==0)//不存在多余的果堆
		{
			q=2*x.first;//两个相同的果堆合并
			if(cnt%2==1)//若果堆数量为单数,本轮合并后会存在多余的1个果堆
			{
				f=1;//标记存在多余1个果堆
				pre=x.first;
			}
			ans+=(cnt/2)*q;
			if(cnt/2!=0)//若果堆x的个数>=2
			{
				st.push({q,cnt/2});
			}
		}
	}
	int mod=1e9+7;
	cout<<ans%mod<<endl;
}