答案中相邻两个数距离 $\le 2$ 的数对至少有 $n/4-1$ 对。因此随意一对距离 $\le 2$ 的数，在答案中相邻的概率约为 $1/8$。随机 $K$ 次的正确率约为 $1-(7/8)^K$，每次可以 $O(n)$ 求出最长的长度，总时间复杂度 $O(Kn)$。
QOJ.ac
QOJ
Discussion #219 for Problem #5045. King
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:16:43
Last updated: 2025-12-13 00:16:47
题解
Comments
No comments yet.