题解 | #D

题目

输入

输出

思路

题目要求合成一堆的代价最小，即要让小的先合在一起，所以考虑用优先队列从小到大排序。

考虑到数据大小，要将同一重量的果子一起处理，可以用pair存储c,w.

对于偶数个相同重量的果子，可以将它们合并，数量减半，然后放入队列里；

对于奇数个，则要保留一个果子，和下一个pair中的果子合并。

每组果子处理完后踢出队列。

完整代码

```#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef pair<long long,int> PII;
int main(){
    int n;
    cin>>n;
    priority_queue<PII,vector<PII>,greater<PII>> pq;
    for(int i=0;i<n;i++){
        int c,w;
        cin>>c>>w;
        pq.emplace(w,c);
    }
    long long ans=0;
    while(true){
        auto [w,c]=pq.top();
        pq.pop();
        if(c>1){
            ans=(ans%mod+c/2*w*2%mod)%mod;
            pq.emplace(w*2,c/2);
            if(c%2){
            pq.emplace(w,1);
            }
        }else if(!pq.empty()){
            auto [w1,c1]=pq.top();
            pq.pop();
            
            ans=(ans%mod+w%mod+w1%mod)%mod;
            pq.emplace(w+w1,1);
            if(c1>1)
                pq.emplace(w1,c1-1);
        
        }else{
            break;
        }
        
    
    }
    cout<<ans<<'\n';
    return 0;
}