官方题解

T5 午枫的彩排

题目大意

有 $n$ 名演员，每位演员有特定的入场时间和退场时间，还有自身的能力值。入场时会帮助所有还在场且能力值小于等于他的演员，他会获得 $w_i-minw$ 的评分。求所有演员的评分。

解题思路

由于演员的入场顺序和入场时间有关，我们可以将所有演员按照入场顺序从小到大排序。

按照能力值为第一关键字，退场时间为第二关键字放到优先队列中，按照从小到大的顺序排序，这样当我们遍历到某一位演员 $x$ 时，优先队列中第一个退场时间大于 $s_x$ 的演员的能力值既是当前场上能力值最小的一位演员。

时间复杂度 $O(nlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define int long long
#define endl '\n'

struct P{
    int a,s,t;
    int id,ans;
};

bool cmp(P a,P b){return a.s<b.s;}
bool cmpid(P a,P b){return a.id<b.id;}

signed main(){
    int n;cin>>n;
    vector<P>p(n+1);
    for(int i=1;i<=n;i++){
        cin>>p[i].a>>p[i].s>>p[i].t;
        p[i].id=i;
    }

    sort(p.begin()+1,p.end(),cmp);
    priority_queue<PII,vector<PII>,greater<PII>>q;//{a[i],t[i]};
    for(int i=1;i<=n;i++){
        while(!q.empty()){
            auto [c,r]=q.top();
            if(r<=p[i].s){
                q.pop();
                continue;
            }

            if(p[i].a>c) p[i].ans=p[i].a-c;
            break;
        }
        q.push({p[i].a,p[i].t});
    }

    sort(p.begin()+1,p.end(),cmpid);
    for(int i=1;i<=n;i++) cout<<p[i].ans<<" ";
}