GESP认证C++编程真题解析 | B3872 [GESP202309 五级] 巧夺大奖

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B3872 GESP202309 五级] 巧夺大奖 - 洛谷

【题目描述】

小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：

1. 游戏分为n nn个时间段，参加者每个时间段可以选择一个小游戏。
2. 游戏中共有n nn个小游戏可供选择。
3. 每个小游戏有规定的时限和奖励。对于第i ii个小游戏，参加者必须在第T i T_iTi​个时间段结束前完成才能得到奖励R i R_iRi​。

小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？

【输入】

输入第一行，包含一个正整数n nn。n nn既是游戏时间段的个数，也是小游戏的个数。约定1 ≤ n ≤ 500 1\le n\le5001≤n≤500。

输入第二行，包含n nn个正整数。第i ii个正整数为T i T_iTi​，即第i ii个小游戏的完成期限。约定1 ≤ T i ≤ n 1\le T_i\le n1≤Ti​≤n。

输入第三行，包含n nn个正整数。第i ii个正整数为R i R_iRi​，即第i ii个小游戏的完成奖励。约定1 ≤ R i ≤ 1000 1\le R_i\le 10001≤Ri​≤1000。

【输出】

输出一行，包含一个正整数C CC，为最高可获得的奖励。

【输入样例】

7 4 2 4 3 1 4 6 70 60 50 40 30 20 10

【输出样例】

230

【算法标签】

《洛谷 B3872 巧夺大奖》 #贪心# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=505;// 最大任务数// 任务结构体structNode{intr;// 任务收益intt;// 任务截止时间}a[N];intn;// 任务数量intans;// 最大总收益boolst[N];// 标记时间点是否被占用// 比较函数：按收益降序排序boolcmp(Node x,Node y){returnx.r>y.r;// 收益高的排前面}intmain(){// 输入任务数量cin>>n;// 输入每个任务的截止时间for(inti=1;i<=n;i++){cin>>a[i].t;}// 输入每个任务的收益for(inti=1;i<=n;i++){cin>>a[i].r;}// 按收益降序排序sort(a+1,a+n+1,cmp);// 贪心算法：为每个任务安排时间for(inti=1;i<=n;i++)// 按收益从高到低处理任务{// 从任务的截止时间向前寻找空闲时间点for(intj=a[i].t;j>=1;j--){if(!st[j])// 如果时间点j空闲{ans+=a[i].r;// 安排任务，累加收益st[j]=1;// 标记时间点被占用break;// 找到时间点，跳出内层循环}}// 如果没有找到合适的时间点，任务不被安排（收益为0）}// 输出最大总收益cout<<ans<<endl;return0;}

【运行结果】

7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 230