[GESP202309 五级] 巧夺大奖

传送门：点我进入

本题是一道典型的贪心问题。

---

本题难度不大，但是最重要的是要首先读懂题目，明白什么是 时间段。

大致题意

有​n个游戏，每个游戏都有对应的一个时间段作为该游戏的 截止时间（意味着在截止时间​k之前的​1-k个时间段都可以进行该游戏）以及对应的 价值。现在需要找出一种最优安排方案使得获得价值最大。

解题思路

首先，我们的 目的 是总价值最大，所以我们可以按照每个游戏的 价值 从大到小进行排序，然后对于每个活动，从后往前遍历一遍时间段，找到一个 最晚的截止时间 就可以完成。

疑问：为什么要将时间 从大到小 进行遍历？

我们如果将每个活动（结束时间为&k&）抽象为一个​[1, k]的区间，并将其放到数轴上如下图：

当多个游戏的奖金相同时，按 时限从大到小遍历 并优先安排，本质上是为了 更合理地分配时间段，避免因高时限游戏占用早时间段而导致低时限游戏无法完成。

如何证明该贪心思路的正确性？

假设存在一个最优解​A与贪心解​B，则有​A≥B。设​A与​B 中第一个奖励不同的任务为​t（按奖励从高到低排序后的第​k个任务）：

在​B中，​t被安排在截止时间内最晚的可用时间段​y；

在​A中，​t被安排在时间​x（x ≤ y，否则 x 超过截止时间，矛盾）。

若​x<y，说明​B中​y在​t之前已被某任务​t‘占用。由于​B 按价值排序，​t的价值​≥t'，因此在​A中交换​t与​t'的时间段：
​t移到​y，​t'移到​x，总奖励不变（甚至更高，若​t'价值​<t）。
调整后​A更接近​B，因此，​A≥B 且 A ≤ B，即贪心策略可得到最优解。

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 505;

int n, flag[N];

struct Node{
  int time, value;  
}a[N];

bool cmp(Node a, Node b){
    return a.value > b.value;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].time;
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i].value;
    }
    sort(a + 1, a + 1 + n, cmp);
  
    int res = 0;
  
    for(int i = 1; i <= n; i++){
        for(int j = a[i].time; j >= 1; j--){
            if(flag[j] == 0){
                res += a[i].value;
                flag[j] = 1;
                break;
            }
        }
    }
    cout << res;
    return 0;
}