题解：P11328 [NOISG 2022 Finals] Gym Badges

· · 题解

题解：P11328 [NOISG 2022 Finals] Gym Badges

双倍经验

P4053 建筑抢修。

题目分析

这道题因为是小于这场比赛的 L 值才能参加，所以在参加相同数量比赛的前提下，使等级最小，这样才能参加尽可能多的比赛。所以可以先参加一些增加等级较少（X 值更小）的比赛，但这也需要参考这个比赛的 L 值，所以可以按每场比赛的 X + L 值按从小到大的顺序排序。

代码实现

可以用一个大根堆来对能参加的比赛的 X 值进行随时的降序排序，如果可以参加这场比赛（当前等级小于比赛的 L 值），就将这场的 X 值放入大根堆，同时增加等级。否则，当无法参加当场比赛时，再判断这场比赛增加的 X 值是否小于了大根堆中增加等级最多的比赛的 X 值。如果小于，就舍弃大根堆中 X 值最大的比赛，参加当前这场（因为要在参加相同数量比赛的前提下，使等级最小）。最终，大根堆中的元素个数就是参加比赛的个数，也就是奖章个数。

AC代码

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<long long>q;
struct bui{
    long long x,l;
}a[500005];
bool cmp(bui a,bui b){
    return a.x+a.l<b.x+b.l;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].l;
    }
    long long flag=0,ans=0;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(flag<=a[i].l){
            flag+=a[i].x;
            q.push(a[i].x);
        }
        else{
            if(a[i].x<q.top()&&q.empty()==0){
                flag-=q.top();
                flag+=a[i].x;
                q.pop();
                q.push(a[i].x);
            } 
        }
    }
    cout<<q.size();
    return 0;
}

蒟蒻的第一篇题解，不合适的地方请指点。