根据数据范围,本题应当使用 O(nlog2n) 或 O(n) 的做法来通过,但是 这篇题解 我按照它的思路模拟一遍后是可以过的,但仔细观察就会发现它的时间复杂度是 n2,且我将它的内层循环里加上统计次数,测试了此极端数据:
10
10 1
9 1
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 15
统计出的次数是 45 次,符合它内层循环共计 10+9⋯+1 的次数。也就是时间复杂度是 O(n2) 的。但是数据过水,应该是随机生成,所以通过了。后来本人想出了优化此题解的办法,因为这篇题解中,它每次循环都向后找到最大的 id 牛(资历最深的),但是这样太耗时了(使得如果有极端数据每次都要找到最后,极端数据也是通过这一点生成的);其实我们如果找到后面到达时间大于它的总时间(代码中 break 的条件)时使用变量 r 记录,然后将 i 到 r 根据 id 排序,一直循环到 r 时,都不用往下找,直接记录答案即可,优化版本时间复杂度为 O(nlog2n),且通过了。强烈建议撤下或修改此题解。