比赛 进阶指南第0章测试 评测结果 AAWWWWWWWW
题目名称 有n种物品 最终得分 20
用户昵称 小福鑫 运行时间 0.420 s
代码语言 C++ 内存使用 4.19 MiB
提交时间 2026-03-14 09:21:43
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,cnt1,cnt2,z[2],f;
struct qq{
    int a,b;
}c[1000001],c1[1000001],c2[1000001];
priority_queue<int> q;
bool cmp(qq x,qq y){
    if(x.a==y.a){
        return x.b<y.b;
    }
    return x.a>y.a;
}
int main(){
    freopen("nit.in","r",stdin);
    freopen("nit.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i].a>>c[i].b;
    }
    for(int i=1;i<=n;i++){
        if(c[i].a>=c[i].b){
            c1[++cnt1].a=c[i].a;
            c1[cnt1].b=c[i].b;
        }
        else{
            c2[++cnt2].a=c[i].a;
            c2[cnt2].b=c[i].b;
        }
    }
    sort(c1+1,c1+cnt1+1,cmp);
    f=1;
    for(int i=1;i<=cnt1;i++){
        while(!q.empty()&&q.top()>c1[i].a){
            z[f]+=q.top();
            q.pop();
            f^=1;
        }
        z[f]+=c1[i].a;
        f^=1;
        q.push(c1[i].b);
    }
    while(q.size()){
        z[f]+=q.top();
        q.pop();
        f^=1;
    }
    for(int i=1;i<=cnt2;i++){
        z[f]+=c2[i].a;
        z[f^1]+=c2[i].b;
    }
    cout<<z[1]-z[0];
}