CSP-J 2019 公交换乘 题解
1. 题意理解
这道题是在模拟一次次出行。
每次出行有三种信息:
* opt=0:坐地铁;
* opt=1:坐公交;
* pri:本次票价;
* t:本次出行时间。
规则是:
坐地铁必须付钱,但会得到一张优惠票。
这张优惠票可以在 45 分钟内坐公交时使用,并且只能用于票价不超过它面值的公交。
每张优惠票只能用一次。
要求我们算出所有出行最少一共花多少钱。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 解题思考
我们按输入顺序处理每一次出行。
如果是地铁:
1. 直接加上本次票价;
2. 得到一张优惠票,放起来。
如果是公交:
1. 先把已经超过 45 分钟的优惠票删掉;
2. 再从剩下的优惠票里找一张能用的;
3. 如果找到了,就使用这张票,不用付钱;
4. 如果找不到,就正常付公交票价。
这里要注意:
如果有多张优惠票都能用,应该使用最早获得的那一张。
所以我们可以用队列维护优惠票,因为队列正好是“先来的先处理”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 部分解
如果数据比较小,可以不用队列。
我们把每一次地铁产生的优惠票都存下来。
每次遇到公交时,就从最早的优惠票开始扫描:
* 如果这张票已经用过,跳过;
* 如果时间超过 45 分钟,跳过;
* 如果票价面值不够,跳过;
* 找到第一张能用的票,就使用它。
这样写最容易理解,因为完全按照题目规则模拟。
但每次公交都可能扫描很多张优惠票,所以复杂度是 O(n^2),只能过小数据。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 核心细节
队列里存还没有使用、也还可能有效的优惠票。
每张优惠票记录两个信息:
处理公交时:
这一步是在删除过期优惠票。
然后扫描队列,找第一张 pri>=公交票价 的优惠票。
为什么要用临时队列?
因为扫描时会把队首弹出来,如果这张票没有使用,就要按原顺序放回去。
如果直接弹出后再放回原队列,可能会打乱优惠票的先后顺序,后面就不一定能使用“最早获得的票”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 例子模拟
假设有三次出行:
第 1 次坐地铁,花 10 元,得到面值 10 的优惠票。
第 2 次坐地铁,花 5 元,得到面值 5 的优惠票。
第 3 次坐公交,票价 6。
队列中优惠票按时间顺序是:
第一张 10>=6,可以用,所以公交不花钱。
总花费是:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 复杂度分析
每次出行只会被处理一次。
优惠票进入队列一次,过期或使用后也只会离开一次。
由于优惠票只有 45 分钟有效,队列里同时存在的有效优惠票数量不会很大。
所以总时间复杂度可以看作:
空间复杂度:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 易错点
1. 坐地铁一定要付钱,并且会产生优惠票。
2. 坐公交不会产生优惠票。
3. 优惠票必须满足两个条件:
4. 一张优惠票只能使用一次。
5. 多张优惠票都能用时,要使用最早获得的那一张。
6. 扫描队列时不能打乱剩余优惠票的顺序。
CSP-J 2019 纪念品 题解
1. 题意理解
有 n 天,m 种纪念品。
第 i 天第 j 种纪念品的价格是 a[i][j]。
一开始有 tot 元钱。
每天可以买纪念品,后面也可以卖掉,目标是让最后手里的钱最多。
本质问题:
如果今天买入,明天卖出,钱可能变多;我们要不断利用每天之间的价格变化,让资金尽量增加。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 解题思考
不要一开始就想很多天一起买卖。
我们可以一段一段看:
对于相邻两天来说:
如果第 i-1 天买第 k 种纪念品,需要花:
到了第 i 天卖掉,可以得到:
这里有一个很容易想不明白的地方:
为什么只考虑“今天买,明天卖”,而不是“今天买,隔很多天以后再卖”?
原因是:每一天都可以把手里的纪念品按当天价格卖掉,也可以再按当天价格买回来。
比如你第 1 天买了某个纪念品,本来想第 3 天卖。
到了第 2 天时,你可以这样理解:
这样做以后,你手里的纪念品数量没有变,后面第 3 天仍然可以卖。
也就是说,跨很多天持有一件纪念品,可以拆成很多段相邻两天的操作:
如果中间有更好的买法,我们还可以换成别的纪念品;如果没有更好的买法,就相当于卖掉再买回原来的。
所以每天结束时,我们只需要关心“当前这些东西按今天价格最多值多少钱”,不需要记录它们到底是哪一天买的。
也就是说,这件纪念品可以看成一个“物品”:
只要钱够,同一种纪念品可以买很多个,所以这是完全背包。
完全背包的意思是:每种物品可以选多次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 部分解
如果数据很小,可以直接暴力枚举。
对于相邻两天,假设当前有 money 元。
我们可以枚举:
只要总花费不超过当前的钱,就是一种合法购买方案。
然后把买到的纪念品在第二天全部卖掉,得到新的钱,再继续处理下一天。
这个做法非常直观,但枚举数量太多,只适合 n,m,tot 都很小的数据。
暴力解的问题是:
每种纪念品可以买 0 个、1 个、2 个……
组合数量会非常大。
所以正解要用完全背包,把这些重复枚举压缩成数组转移。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 状态设计
处理从第 i-1 天到第 i 天时,设:
表示:
手里最多有 j 元钱时,经过“第 i-1 天买、第 i 天卖”后,最多能变成多少钱。
为什么初始化为:
因为你可以什么都不买。
如果什么都不买,那么有 j 元,第二天还是 j 元。
这就是最基础的情况。
然后枚举每种纪念品 k:
如果当前有 j 元,可以拿出 a[i-1][k] 元买一个第 k 种纪念品。
买完后剩下 j-a[i-1][k] 元。
这部分钱经过处理后最多能变成:
再加上这个纪念品明天卖出的价格:
所以转移是:
这里 j 从小到大枚举,是因为同一种纪念品可以买多次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 例子理解
假设当前有 10 元。
某种纪念品今天价格 3,明天价格 5。
如果买 1 个:
如果买 3 个:
原本 10 元就可能变成:
所以同一种纪念品确实可能买很多个,这就是为什么要用完全背包。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 复杂度分析
外层枚举天数,共 n-1 次。
每相邻两天之间,要枚举 m 种纪念品,并枚举当前资金 tot。
所以时间复杂度大约是:
题目中初始资金范围不大,且资金增长也在可接受范围内,所以可以通过。
空间复杂度:
因为背包数组只需要一维。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 易错点总结
1. dp[j] 初始化不能全设成 0。
因为不买纪念品时,钱不会消失,应该有 dp[j]=j。
2. 循环 j 要从小到大。
同一种纪念品可以买多次,所以是完全背包。
3. 买入价格用前一天的价格。
也就是:
4. 卖出价格用后一天的价格。
也就是:
5. 每处理完相邻两天,要更新当前资金:
这样下一天才是在新的资金基础上继续赚钱。