申请撤下题解
查看原帖
申请撤下题解
1027540
GLr137_2025BL楼主2025/7/21 09:29

根据数据范围,本题应当使用 O(nlog2n)O(n \log^2 n)O(n)O(n) 的做法来通过,但是 这篇题解 我按照它的思路模拟一遍后是可以过的,但仔细观察就会发现它的时间复杂度是 n2n ^ 2,且我将它的内层循环里加上统计次数,测试了此极端数据:

10
10 1
9 1
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 15

统计出的次数是 4545 次,符合它内层循环共计 10+9+110 + 9 \dots + 1 的次数。也就是时间复杂度是 O(n2)O(n ^ 2) 的。但是数据过水,应该是随机生成,所以通过了。后来本人想出了优化此题解的办法,因为这篇题解中,它每次循环都向后找到最大的 id 牛(资历最深的),但是这样太耗时了(使得如果有极端数据每次都要找到最后,极端数据也是通过这一点生成的);其实我们如果找到后面到达时间大于它的总时间(代码中 break 的条件)时使用变量 r 记录,然后将 iirr 根据 id 排序,一直循环到 r 时,都不用往下找,直接记录答案即可,优化版本时间复杂度为 O(nlog2n)O(n \log^2 n),且通过了。强烈建议撤下或修改此题解。

2025/7/21 09:29
加载中...