官方题解｜龟兔赛跑

题目解析

题目给出了乌龟和兔子的行进速度，并且特别的：兔子每跑 $10$ 分钟会根据自己和乌龟的位置来决定是否休息。

我们可以根据以上信息，按照时间顺序来模拟整场比赛：

1. rabbit 表示当前兔子跑过的距离；
2. turtle 表示当前乌龟跑过的距离；
3. i 表示当前时间；
4. 对于一般情况，我们使用「循环」模拟每分钟发生的事件：兔子乌龟都向前跑；
5. 每跑 $10$ 分钟，判断下兔子和乌龟的行进距离，如果兔子在乌龟前兔子开始休息，我们使用一个「子循环」来处理兔子休息时的事件：乌龟向前跑。
6. 不论是「循环」还是「子循环」一旦时间到达 $N$ 分钟，立刻结束比赛，结束所有循环。
7. 根据 rabbit 和 turtle 的大小关系来判断比赛结果。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        int rabbit = 0, turtle = 0, i = 0;
        while (i < n) {
            rabbit += 9;
            turtle += 3;
            i++;
            if (i % 10 != 0 or rabbit <= turtle) continue;
            for (int j = 0; j < 30 and i < n; j++, i++)
                turtle += 3;
        }
        if (rabbit > turtle) 
            cout << "^_^ " << rabbit << '\n';
        else if (rabbit < turtle)
            cout << "@_@ " << turtle << '\n';
        else
            cout << "-_- " << rabbit << '\n';
    }
    return 0;
}

复杂度分析

按分钟模拟事件，时间复杂度为 $\mathrm{O}(N)$。