题解 P11328

· · 题解

题意：

有一些徽章，想要获得一个徽章必须等级不超过某一个值，获得一个徽章会提升一定的等级，问最多获得多少个徽章。

思路：

板题的反悔贪心，把徽章按照 X_i+L_i 的获得后最高等级排序。

维护一个大根堆，从大到小给所有徽章按等级数排序。然后顺序遍历所有徽章，如果当前徽章本身就可以获得，直接加入大根堆。如果当前徽章不能获得，将它和堆里最大的数进行比较。如果它比堆里最大的徽章等级数少，而且将堆里最大的徽章等级数量去掉后可以获得当前的徽章，那就可以直接将堆里最大的值抛掉，新的徽章压入堆。

最终结果即为堆的大小。

可以证明上述方法正确，在需要更换堆中元素时总时长不减，同时徽章获得数只会单调递增。时间复杂度 O(Tn\log n)。

注意开 long long。

代码如下：

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5e5+5;
int T,n;
struct JOB{long long s,t;}a[N];
bool operator<(JOB x,JOB y){return x.t==y.t?x.s<y.s:x.t<y.t;}
bool cmp(JOB x,JOB y){return x.s+x.t<y.s+y.t;}
priority_queue<JOB,vector<JOB>,less<JOB> >q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].t);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].s);
    sort(a+1,a+n+1,cmp);
    long long curt=0;
    for(int i=1;i<=n;i++){
        if(curt<=a[i].s){
            q.push(a[i]);
            curt+=a[i].t;
        }
        else{
            JOB u=q.top();
            if(a[i].t<u.t&&curt-u.t<=a[i].s){
                q.pop();
                curt-=u.t;
                q.push(a[i]);
                curt+=a[i].t;
            }
        }
    }
    printf("%d\n",q.size());
    return 0;
}

THE END