1 条题解
-
2XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2023-10-13 10:26:48
多重影分身之术(duplication)
问题的答案具有单调性: 因为总的时问越长,每个影分身能覆盖的范围就越大,从而能被捡到的卷轴也就越多,所以直接考虑二分
对于每个影分身,它走的路线显然至多只会改变一次方向: 每个影分身要么先向左走一段后转身一直向右走,要么先向右走一段后转身一直向左走,从左向右考虑每个影分身,它能走的总距离是被二分值确定的,如果最左的影分身左侧还有卷轴,则该卷轴一定是由该影分身去拾取,否则该影分身可以选择径直向右走,无论哪种情况,都可以视为上述两种路线中选择一种使得向右延伸的距离尽可能远
那么从左到右对所有的影分身归纳考虑,每个影分身在保证左侧所有卷轴都被拾取的情况下尽可能贪心向右走,如果不能保证拾取卷轴则判定该二分值不可行,若所有卷轴都被拾取则判定该二分值可行最终总时问复杂度\(O((n+m)logmax(x_i,y_i))\)
- 1
信息
- ID
- 1021
- 难度
- 10
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者