[NowCoder11253L]WeChat Walk

WeChat Walk

https://ac.nowcoder.com/acm/contest/11253/L

的为大点, 的为小点。由于总步数 且每个人的步数是与时间正相关的,考虑按步数 从大到小枚举,设 时刻走到步数 是冠军当且仅当 相邻的点在之前没有更新过步数或者更新的时刻大于 ,设 表示 最近一次更新步数的时刻, 表示 上一次更新步数的时刻,初值均为最终时刻
保持步数为 且为冠军的持续时间为 ,若 为小点则 可以暴力计算,若 为大点,考虑直接维护这个结果(记为 ),即每个点步数更新时,枚举其周围所有大点 来更新 。由于大点数量 ,故总复杂度为 ,取 即可。时间复杂度

代码

全部评论

相关推荐

Beeee0927:正确的建议
点赞 评论 收藏
分享
03-12 15:34
已编辑
北京邮电大学 Java
呓语0613:老哥你这黑马点评改造是在哪里看的
点赞 评论 收藏
分享
评论
7
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务