题目解析
题目给出了乌龟和兔子的行进速度,并且特别的:兔子每跑 101010 分钟会根据自己和乌龟的位置来决定是否休息。
我们可以根据以上信息,按照时间顺序来模拟整场比赛:
1. rabbit 表示当前兔子跑过的距离;
2. turtle 表示当前乌龟跑过的距离;
3. i 表示当前时间;
4. 对于一般情况,我们使用「循环」模拟每分钟发生的事件:兔子乌龟都向前跑;
5. 每跑 101010 分钟,判断下兔子和乌龟的行进距离,如果兔子在乌龟前兔子开始休息,我们使用一个「子循环」来处理兔子休息时的事件:乌龟向前跑。
6. 不论是「循环」还是「子循环」一旦时间到达 NNN 分钟,立刻结束比赛,结束所有循环。
7. 根据 rabbit 和 turtle 的大小关系来判断比赛结果。
AC代码
复杂度分析
按分钟模拟事件,时间复杂度为 O(N)\mathrm{O}(N)O(N)。