信息学奥赛一本通高手训练 1672：游戏通关贪心算法

长春高老师编程

777人浏览 · 2024-02-29 21:51:06

长春高老师编程 · 2024-02-29 21:51:06 发布

1672：游戏通关

时间限制: 1000 ms 内存限制: 262144 KB

【题目描述】

XY在玩一个包含N个任务的游戏。每个任务完成时限为Ti（你可以认为还没开始做任务时的时间为0），奖励为Wi。由于XY技术的娴熟以及任务的简单，对于每个任务，他都可以在一个单位时间内完成。

XY想要知道他能够获得的最多的奖励。

【输入】

第一行一个整数N，表示需要完成的任务数目。

接下来N行，每行两个整数T、W，分别表示完成这个任务的最后期限和完成这个任务后获得的奖励。

【输出】

输出数据有且仅有一行，只包含一个整数，表示最多获得的奖励。

【输入样例】

2
1 5
1 4

【输出样例】

【提示】

【样例输入2】

【样例输出2】

【样例解释2】

对于样例2，XY可以选择完成任务1、3、4 和5，这样他可以获得奖励15。

【数据规模及约定】

对于10%的数据，N≤100，Ti≤100，Wi≤2000。

对于30%的数据，N≤1000，Ti≤5000，Wi≤2000。

对于50%的数据，N≤10000，Ti≤20000，Wi≤2000。

对于100%的数据，N≤200000，Ti≤200000，Wi≤2000。

解析：

详见代码：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node {
    int t;
    int w;
};
node a[200005];
bool cmp(node x,node y){
    return x.t>y.t;
}
priority_queue <int> q;//大根堆
long long ans=0;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].t>>a[i].w;
    }
    sort(a+1,a+n+1,cmp);//按期限从大到小排序
    int p=1;
    for(int i=n;i>=1;i--){//枚举时间从大到小
        while (a[p].t>=i){//将期限内可以得到奖励的任务加入大根堆
            q.push(a[p].w);
            p++;
        }
        if (!q.empty()){//取期限范围内最大奖励的任务
            ans+=q.top();
            q.pop();
        }
    }
    cout<<ans;
    return 0;
}