竞赛讨论区 > D题果子那题只过了15个点求调,感谢
头像
bounce__back
发布于 02-14 08:06 福建
+ 关注

D题果子那题只过了15个点求调,感谢

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5+10;

const ll M = 1e9+7;

struct P{

ll c,w;

bool operator<(const P &a)const{

return w > a.w;

}

}a[MAXN];

int main(){

ios::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

int n;

ll tot,ans;

tot = ans = 0;

cin >> n;

for (int i = 1;i <= n;i++){

cin >> a[i].c >> a[i].w;

tot += a[i].c;

}

priority_queue<P> pq;

for (int i = 1;i <= n;i++){

pq.push(a[i]);

}

ll ind = 0;

while (tot > 1 && !pq.empty()){

auto [c,w] = pq.top();

pq.pop();

//cout << c << ' ' << w << '\n';

if(c == 0) continue;

if(c == 1){

tot -= 1;

auto [cc,ww] = pq.top();

pq.pop();

ans += ww+w;

pq.push({1,ww+w});

if(cc > 1){

pq.push({cc-1,ww});

}

continue;

}

tot -= c/2;

pq.push({c/2,w*2});

ans += (c/2)*(w*2);

ans %= M;

c %= 2;

if(c == 1){

pq.push({1,w});

}

}

cout << ans << endl;

return 0;

}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐