[GESP202309 五级] 巧夺大奖

GESP编程共123题，本题是整站第1383题，已经有人完成了本题，加油！

题目描述

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

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

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

输入第二行，包含 n 个正整数。第 i 个正整数为 Ti，即第 i 个小游戏的完成期限。约定 1≤Ti≤n。

输入第三行，包含 n 个正整数。第 i 个正整数为 Ri，即第 i 个小游戏的完成奖励。约定 1≤Ri≤1000。

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

输入 #1

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

输出 #1

样例解释 1

7 个时间段可分别安排完成第 4、2、3、1、6、7、5 个小游戏，其中第 4、2、3、1、7 个小游戏在期限内完成。因此，可以获得总计 40+60+50+70+10=230 的奖励。

【题目大意】

在n个时间段内完成n个小游戏，每个小游戏完成的时间和获得奖励不同，如何选择小游戏使得最后获得奖励最高。

需要注意这句话的理解“对于第i个⼩游戏，参加者必须在第Ti个时间段结束前完成才能得到奖励”，也就是在第1~Ti个时间段范围之内，其中任意一个时间段都可以完成第i个游戏。

【考纲知识点】

贪心算法、数组、sort函数

【解题思路】

本题采用贪心策略，想要获得的最高奖励，优先完成获得奖励多的游戏，同时考虑在完成第i个游戏的时候，第1~Ti个时间段是否被占用，如果都被占用，那么该游戏就不能被完成。解题步骤如下：

1)首先创建结构体game用于保存每个游戏的信息，包括游戏时间期限T和对应的奖励R，并创建games[505]用于保存n个游戏的信息;

2)按题目要求输入数据，并保存在games数组中;

3)根据游戏的奖励，对数组games进行降序排序;

4)遍历排序后的数组games，依次判断第i个游戏是否能完成，如果能完成就累加当前游戏的奖励games[i].R;

5)判断游戏是否能完成可以使用一个数组进行标记，标记第1n个时间段是否被占用，如果第i个游戏的可完成时间段为第1Ti，如果该范围都被占用，则第i个游戏无法完成。

【参考程序】

本站题目仅供学习，GESP版权归CCF所有，如有侵权请联系删除。站长陈老师QQ及微信:208234。