Kattis Left and Right：Python 解法出现 TLE 如何优化

2026-11-04排障赵师傅

结论

TLE 通常出在这句代码上：

group += i

Python 字符串不可变。连续拼接很长的 L 或 R 分组时，程序会反复创建和复制字符串，最坏时间复杂度可达 (O(n^2))。

可以把 1, 2, ..., n 中每段连续 L 对应的区间反转，将时间复杂度降到 (O(n))，足以处理 (n \le 2 \times 10^5)。由于输入只有两行，使用 fast input 的提升有限，批量输出的效果更明显。

为什么可以反转连续的 `L`

方向字符表示相邻元素之间的大小关系：

L：下一个房屋编号更小，即 answer[i] > answer[i + 1]
R：下一个房屋编号更大，即 answer[i] < answer[i + 1]

例如：

s = RLLRL

先写出自然递增序列：

1 2 3 4 5 6

连续的 LL 要求对应的三个数严格递减，所以反转 2 3 4：

1 4 3 2 5 6

最后一个 L 对应 5 6，反转后得到：

1 4 3 2 6 5

这个结果也是字典序最早的合法序列。

假设当前位置后面连续有 (k) 个 L，那么它后面需要放置 (k) 个更小的数。要让当前位置的数尽可能小，就要选择剩余数字中的第 (k+1) 小值，再把前 (k) 个较小值按降序放在后面，效果正好等同于反转这一段。

(O(n)) 解法

无需提前构造字符串分组。遇到 R 或扫描到末尾时，直接把当前区间倒序加入结果：

import sys

n = int(sys.stdin.buffer.readline())
s = sys.stdin.buffer.readline().strip().decode()

answer = []
start = 1

for end in range(1, n + 1):
    # s[end - 1] 表示 answer[end] 与 answer[end + 1] 的关系。
    # end == n 时没有下一个字符，需要把最后一段也输出。
    if end == n or s[end - 1] == "R":
        answer.extend(range(end, start - 1, -1))
        start = end + 1

sys.stdout.write("\n".join(map(str, answer)) + "\n")

以 RLLRL 为例，代码会依次处理：

R    -> 输出 1
LLR  -> 输出 4 3 2
L    -> 输出 6 5

最终结果为：

复杂度

每个房屋编号只会加入结果一次：

时间复杂度：(O(n))
空间复杂度：(O(n))

程序必须输出 (n) 个整数，因此 (O(n)) 已经是渐进意义上的最优时间复杂度。

原代码中较慢的地方

1. 循环拼接字符串

group += i

分组较长时，这种写法会产生大量中间字符串。对于下面这样的极端输入：

LLLLLLLLLLLL...

字符复制量可能接近：

[ 1 + 2 + 3 + \cdots + n = O(n^2) ]

某些 Python 实现可能会优化部分拼接操作，但代码不应依赖这种行为。

2. 无需构造分组

原代码先扫描字符串生成 groups，再逐个处理这些分组。这里实际只需找到每段 L 的结束位置，一次扫描即可完成。

3. 输出方式有额外开销

print(*seq, sep="\n")

这会把整个列表展开为位置参数，然后逐个转换并写入。需要输出几十万个整数时，更适合一次性拼接后写入：

sys.stdout.write("\n".join(map(str, answer)) + "\n")

4. fast input 影响有限

输入只有一个整数和一个长度为 (n-1) 的字符串，即使使用普通 input()，也只会读取两次。sys.stdin.buffer 能减少少量开销，却无法解决 (O(n^2)) 的处理过程。需要调整的是字符串分组方法和输出方式。