C++贪心算法：巧用锦囊，挑战闯关游戏最高分！

你参加了一个闯关游戏，游戏共有 n 关，每关可以选择使用一个锦囊来获得分数加成，但每个锦囊有有效期和分数。如何合理安排锦囊的使用，才能获得最高分呢？

本文将带你解析这道经典的C++算法题，并提供详细的代码实现，助你提升算法思维能力。

题目描述

你参加了一个闯关游戏，游戏共有 $n$ 关，每关你需要挑选一个锦囊，游戏开始时，你共有 $m$ 个锦囊。

锦囊是有有效期的，第 $i$ 个锦囊的有效期截至第 $a_i$ 关，第 $a_i+1$ 关及以后就再也不能使用这个锦囊。

锦囊还有对应的分数，第 $i$ 个锦囊的分数是 $b_i$，使用这个锦囊过关就可以获得 $b_i$ 的分数；不使用锦囊过关则那一关不获得分数；每个锦囊只能使用至多 $1$ 次。

合理安排锦囊的使用，求闯过 $n$ 关后的最大得分。

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n,m$（$n,m \le 1000$）。

接下来 $m$ 行，每行输入两个正整数 $a_i$（$a_i \le n$）和 $b_i$（$b_i \le 10^6$）。

输出格式

输出到标准输出。

输出一个整数，表示最大得分。

样例

输入 #1

6 84 132 146 52 76 41 31 86 1

输出 #1

解题思路：贪心算法

本题可以使用贪心算法求解，即每一步都选择当前最优的策略，最终得到全局最优解。

具体步骤：

从后往前遍历每一关。2. 对于每一关，选择当前可用锦囊中分数最高的锦囊使用。3. 如果没有可用锦囊，则不使用锦囊。

**代码实现：**c++#include<bits/stdc++.h>using namespace std;// 本题思路：从后往前填充关卡，每次找当前能填的最高分的锦囊const int N = 1005, M = 1005;struct Data{ int score, timee; bool use; // use记录锦囊是否用过} a[M]; // a[] 存储锦囊int ans, n, m; int main(){ scanf('%d%d', &n, &m); for(int i = 1; i <= m; ++i) scanf('%d%d', &a[i].timee, &a[i].score); for(int i = n; i >= 1; --i){ // i枚举的是第i关 int id = 0; // id存储目前可选锦囊中分数最高的锦囊的下标 for(int j = 1; j <= m; ++j){ // j枚举的是锦囊的下标 if(a[j].timee >= i && !a[j].use){ // 这个锦囊在第i个时刻还没有过期 if(id == 0 || a[j].score > a[id].score) id = j; // 做一次更新操作 } } if(id != 0){ ans += a[id].score; a[id].use = true; } } printf('%d ', ans); return 0;}

总结

本题是一道经典的贪心算法题，通过从后往前遍历关卡，并选择当前可用锦囊中分数最高的锦囊使用，可以保证最终获得最大得分。希望本文能帮助你理解贪心算法的思想，并提升算法解题能力。