G5002 [GESP202309 五级] 巧夺大奖 题解

知识点：贪心、优先队列、排序。

解题思路

按截止时间升序处理任务，加入收益小根堆；若已选数量超过当前截止时间，就删去最小收益。

为什么正确

每个前缀能安排的任务数受截止时间约束，超容量时保留最大收益集合可通过交换维持最优。

易错点

按时间而非收益直接排序；删除堆中最小收益，不是当前任务。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>t(n),a(n);
    for(int &x:t)cin>>x;
    for(int &x:a)cin>>x;
    vector<pair<int,int>>v;
    for(int i=0;i<n;i++)v.push_back({t[i],a[i]});
    sort(v.begin(),v.end());
    priority_queue<int,vector<int>,greater<int>>q;
    for(auto [t,x]:v) {
        q.push(x);
        if((int)q.size()>t)q.pop();
    }
    int ans=0;
    while(q.size()) {
        ans+=q.top();
        q.pop();
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。