UOJ Logo user114514的博客

博客

关于本次T2(#1230)可以被 O(n^3) 通过一事

2022-10-03 05:30:12 By user114514

rt qwq

思路就是如果目标地点在两人围成的区间之外,就贪心地让最近的人移过去,否则就分别搜索两个人移动到目标的情况

如果一定要让我对我这个算法分类,我认为这是一种写得非常奇怪的记忆化搜索

容易证明这个东西复杂度的上限是 $O(n^3)$ (两个人位置的取值分别有 $n$ 种情况,然后又要扫 $n$ 遍)

所以我认为这个题目的数据造得并不是很优秀,希望以后的出题人们能够引以为戒,防止我这种申必写法卡过去(还跑得贼快

评论

hjxhjx
可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。
Reliauk
你是真的强
hjxhjx
可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@”。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。