题解 | #智乃的果子#

题目解析

这道题目是一个哈夫曼编码问题，也被称为合并果子问题。核心在于利用贪心策略和优先队列（小根堆）来寻找最小的合并代价

我们应该总是优先合并当前重量最小的两堆果子。 为了高效地找到当前最小的两堆果子，我们需要使用优先队列，并且需要将其设置为小根堆（即堆顶元素最小）

代码演示

#include<bits/stdc++.h>
using namespace std;
//#define int long long 
#define endl '\n'
const int N = 500010;
const int mod=1000000007;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
void solve(){
	int n,c,w,total=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c>>w;
		q.push({w,c});
		total+=c;
	}
	if(total<=1){
		cout<<"0"<<endl;
		return;
	}
	int sum=0;
//	while(total>1){
//		pair<int,int>pii=q.top();
//		q.pop();
//		if(pii.second>=2){
//			int tmp1=pii.second/2;
//			sum+=2*tmp1*pii.first;
//			sum%=mod;
//			q.push({2*pii.first,tmp1});
//			int tmp2=pii.second%2;
//			if(tmp2==1){
//				q.push({pii.first,1});
//			}
//			total-=tmp1;
//		}else{
//			pair<int,int>pii2=q.top();
//			q.pop();
//			pii2.second--;
//			sum+=pii.first+pii2.first;
//			sum%=mod;
//			q.push({pii.first+pii2.first,1});
//			if(pii2.second>0){
//				q.push({pii2.first,pii2.second});
//			}
//			total--;
//		}
//	}
	while(total>1){
		auto [w,c]=q.top();
		q.pop();
		if(c>=2){
			int tmp1=c/2;
			sum+=2*w*tmp1;
			q.push({2*w,tmp1});
			if(c%2){
				q.push({w,1});
			}
			total-=tmp1;
		}else{
			auto [w2,c2]=q.top();
			q.pop();
			c2--;
			sum+=w+w2;
			q.push({w+w2,1});
			if(c2){
				q.push({w2,c2});
			}
			total--;
		}
	}
	sum%=mod;
	cout<<sum<<endl;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}