1 条题解
-
0
测试点 1∼2
从低到高枚举等级暴力搜索即可。
测试点 3~7
可以发现如果第一个买的游戏编号是,最后一个买的游戏编号是,那么能且只能确定从到之间所有没买的游戏都一定比买了的游戏等级低。
这样就可以用拓扑排序去做,从能确定的低等级游戏到高等级游戏之间连一条边,每个点的最低等级是所有入度里最高的最低等级加,最后输出最高的最低等级。
时间复杂度是。
测试点 8~10
注意到我们的时间复杂度主要体现在建边上,一轮浏览建边需要的时间复杂度就有。
对于每次建边,我们可以建立一个虚点,所有没有被选上的游戏做虚点的入度,选上的游戏做虚点的出度。
这样一轮连边的时间复杂度为,总时间复杂度为O(mn),要注意虚点不会增加层数。
- 1
信息
- ID
- 51
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者