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

· · 题解

Solution

题目传送门

题目分析

这道题是一个经典的贪心算法问题，要求在有限的时间段内完成尽可能多的小游戏以获得最大的奖励。每个游戏有一个截止时间和一个奖励值。目标是制定一个策略来选择游戏，以最大化总奖励。

题目思路

这道题的关键在于如何选择和安排游戏。贪心就提供了一个有效的解决方案：优先考虑奖励最高的游戏。

解题步骤

  1. 将所有游戏按照奖励值（r）降序排序。
  2. 使用一个布尔数组来跟踪每个时间段是否已经被游戏占用。
  3. 按排序后的顺序遍历。对于每个游戏，从其截止时间开始向前寻找第一个空闲的时间段进行安排。
  4. 每次成功安排一个游戏，累加其奖励到总奖励中。

AC Code

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 500 + 10;
bool flag[maxn] = {false};
struct Node{
    int r, d; //r 表示游戏的奖励，d表示游戏的截止时间
} a[maxn];
bool cmp(const Node& x, const Node& y){
    return x.r > y.r;
}
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i].d;
    }
    for(int i = 0; i < n; ++i) {
        cin >> a[i].r;
    }
    sort(a, a + n, cmp);
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int t = a[i].d; t > 0; --t) {
        //如果找到一个空闲的时间段，那么安排游戏
            if(!flag[t]) {
                flag[t] = true; //标记时间段为已占用
                ans += a[i].r; //累加奖励
                break; //跳出循环
            }
        }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度：O(n^2)，可以通过本题。