第七课-月赛讲解

3 月月赛讲解

题目链接：http://oj.oldmoon.cn/contest/67c800e3efdf66c1dde64e58

题目概览

题目讲解

第一题：A+B 问题

送分题

第二题：宝箱

原题，课上讲过。

第三题：Even More Odd Photos

数学知识

该题很有思维性，通过奇数和偶数的特性解题。

首先明确以下三点公理：

1. 奇 + 奇=偶
2. 奇 + 偶=奇
3. 偶 + 偶=偶（本题用不到）

算法设计

贪心：每一组的奶牛尽可能少，这样才能尽可能分出更多的组。

1. 因为我们只关心编号的奇偶性，先统计奇数和偶数的个数，记编号为奇数的牛的数量为 odd。
2. 如果偶数数量大于奇数，只保留 odd+1 个偶数，多的也没用（将他们合并进其它偶数组）。可以分出 2*odd+1 组。
3. 如果偶数数量等于奇数，刚好可以分出 2odd 组
4. 如果偶数数量小于奇数数量，可以将两个奇数相加变成偶数，减少奇数的数量，增加偶数的数量。
   1. 什么时候中止？

拿样例数据试一试！

• 有没有人觉得样例数据的输出应该为 4？
  • 需要将每头奶牛分到恰好一组中！不能有未分组的奶牛。

编写代码

第一版：更好理解

• 11-13：先把奇数 > 偶数的情况，转化为偶数 >=奇数的情况
• 14-15：处理偶数=奇数的情况。
• 17-18：处理偶数 > 奇数的情况。

• 第二版：11-14 行的代码写的很精简，但是牺牲了一定的代码可读性。我们也可以按照算法设计中的 2-4，逐步实现。
  • 11-13：先把奇数 > 偶数的情况，转化为偶数 >=奇数的情况
  • 处理偶数 > 奇数和偶数=奇数的情况。

第四题：GESP202309 五级 巧夺大奖

理解题目

有同学可能觉得读题很难，因为有很多代数符号，Ti，Ri。

重新描述：有 n 个项目，每个项目有规定时限，时限内完成有奖金，求最多能得到多少奖金

算法设计

由于完成每一个游戏都只需要一个时间段，因此我们应优先完成奖金较大的游戏，在能够完成此任务的同时，我们应优先选择较大的时间段（拖到任务截止的时候才做），所以我们可以利用贪心的思想来对该题进行求解。

对于样例输入 1，我们首先完成任务 1（70 奖励，时间 4 之前完成），应该把它放在最晚的时间段 4 来做。这样我们空出来的时间段还有1,2,3,5,6,7。如果放在时间段 1 来做，空出的时间段是2,3,4,5,6,7。明显1,2,3,5,6,7拿到的分会大于等于2,3,4,5,6,7。

编写代码

• line1-9：初始化布尔数组，创建一个复合数据结构 a
  • a 是一个列表，里面每一个子元素是元组，元组的长度固定为 2，第一个元素是任务的奖励分数，第二个元素是任务截止时间。
  • 将这 n 个元组，按奖励分数从大到小降序排序。
• line11-line18
  • 从奖励最高的任务出发，把每个任务放在最晚的时刻去完成，并计算总得分。
  • 怎样找到最晚完成时刻？使用 used 数组，usedi表示 i 时刻是否被其他任务占用，如果占用，就去找 i-1，直到没有一个时刻可以满足条件，此任务就不需要完成了。

完整版预览：https://qthnxv199t.feishu.cn/docx/JuwAdaACBowzgdxUlMbcBnWvndd

• 更多题目（平均难度也更高）
  • 题单：https://www.luogu.com.cn/training/list?type=select&page=1
  • 贪心题单：https://www.luogu.com.cn/training/5199#information
• 查看题解，测试数据。
• https://www.luogu.com.cn/problem/list 搜索：深中光明 python 社团，加入团队