比赛 20251001国庆欢乐赛1 评测结果 AAAAAAAAAA
题目名称 有n种物品 最终得分 100
用户昵称 彭欣越 运行时间 0.166 s
代码语言 C++ 内存使用 4.21 MiB
提交时间 2025-10-01 08:59:37
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n;
ll sum1,sum2;
struct node {
    ll a,b;
}s[N];
queue<ll>q1,q2;
bool cmp (node x,node y) {
    return x.a-x.b>y.a-y.b;
}
int main () {
    freopen("nit.in","r",stdin);
    freopen("nit.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> s[i].a >> s[i].b;
    }
    sort(s+1,s+n+1,cmp);
    int cnt=1,sum=0;
    while (cnt<=n) {
        sum++;
        if (s[cnt].a-s[cnt].b<0) {
            if (sum%2==1) {
                if (!q1.empty()) {
                    sum1+=q1.front();
                    q1.pop();
                }else{
                    sum1+=s[cnt].a;
                    q2.push(s[cnt].b);
                    cnt++;
                }
            }else{
                if (!q2.empty()) {
                    sum2+=q2.front();
                    q2.pop();
                }else{
                    sum2+=s[cnt].a;
                    q1.push(s[cnt].b);
                    cnt++;
                }
            }
        }else{
            if (sum%2==1) {
                sum1+=s[cnt].a;
                q2.push(s[cnt].b);
                cnt++;
            }else{
                sum2+=s[cnt].a;
                q1.push(s[cnt].b);
                cnt++;
            }
        } 
    }
    while (!q1.empty()) {
        sum1+=q1.front();
        q1.pop();
    }
    while (!q2.empty()) {
        sum2+=q2.front();
        q2.pop();
    }
    cout << sum1-sum2 <<endl;
    return 0;
}