本文详解 kattis 题目 “left and right” 的最优解法：在给定 n−1 个 'l'/'r' 移动方向的前提下，构造字典序最小的房屋访问序列，时间复杂度 o(n)，避免 tle。
本文详解 kattis 题目 “left and right” 的最优解法：在给定 n−1 个 'l'/'r' 移动方向的前提下，构造字典序最小的房屋访问序列，时间复杂度 o(n)，避免 tle。
问题本质与关键洞察
该题并非模拟路径，而是逆向构造：给定相邻访问位置的相对方向（如从位置 a 到 b 是左移 'L' 或右移 'R'），需输出所有合法排列中字典序最小的一个。
核心观察在于：
- 每个 'R' 表示下一个位置比当前更大；每个 'L' 表示下一个位置更小。
- 字典序最小 → 应尽可能让靠前的位置取最小可能值。
- 最优策略是分段贪心构造：将方向字符串按连续相同字符分组（如 "RLLRL" → ["R", "LL", "R", "L"]），每组对应一段单调递增或递减的数值序列，且整个序列必须使用 1~n 的每个整数恰好一次。
更高效的视角是：把方向串看作对 n 个位置的相对大小约束链，而字典序最小解等价于——在满足所有 a[i] a[i+1]（当 s[i]=='L'）的前提下，使 a[0] 尽可能小，其次 a[1] 尽可能小，依此类推。
但直接 DP 或 DFS 显然超时（O(2ⁿ)）。真正高效的做法是扫描方向串，识别极值点并分段填充：
- 每个连续 'R' 段意味着后续位置严格递增 → 对应一段升序子列；
- 每个连续 'L' 段意味着后续位置严格递减 → 对应一段降序子列；
- 关键在于：为保证字典序最小，我们应从全局最小未用数开始分配，并让每段“尽可能早地消耗小数字” —— 这自然导向一种“延迟分配 + 反向填充”的技巧：对每个 'L' 段，我们先预留空间，到最后统一从大到小填入；而 'R' 段则可顺序填入。
然而，Kattis 官方推荐及实践验证的最优 O(n) 构造法是：
✅ 不显式分组，而是两次扫描确定每个位置的“右侧最长连续 L 长度”（即以该位置为起点向右能延伸多少个 L），从而决定其值 = 起始编号 + 向右 L 段长度。
但更简洁、更易实现、且同样 O(n) 的方法是：按方向变化点切分，对每段 L/R 连续块，直接生成对应递增/递减的整数区间，并利用 Python 的 range() 和 extend() 批量输出——这正是优化后代码的核心。
优化后的高效实现（O(n) 时间，无额外空间）
以下代码完全规避了字符串拼接、列表重复 append、中间 groups 存储等低效操作，直接流式输出：
import sys
def main():
data = sys.stdin.read().splitlines()
n = int(data[0])
s = data[1].strip() if len(data) > 1 else ""
# 若首字符为 'R'，第一个位置必须是 1（最小可能）
if s and s[0] == 'R':
print(1)
i = 0
while i i:
# 输出 i+2 到 j+1（共 j-i 个数，升序）
print(*range(i + 2, j + 2), sep="\n")
i = j
# 处理连续 'L' 段
if i <blockquote>
<p>✅ <strong>关键优化点说明</strong>：</p>
<ul>
<li>使用 sys.stdin.read().splitlines() 一次性读入，避免逐行 I/O 开销；</li>
<li>range(start, stop, step) 直接生成整数序列，print(*..., sep="\n") 批量输出，比循环 print() 更快；</li>
<li>while 循环内按字符类型跳转，时间复杂度严格 O(n)，无冗余存储；</li>
<li>完全避免字符串拼接（group += i 是 O(k²)）、避免构建中间 groups 列表、避免多次 append。</li>
</ul>
</blockquote><h3>注意事项与常见陷阱</h3>
- 不要忽略边界情况：当 n=2 时，s 长度为 1，需确保 range 参数不越界；
- 字典序最小 ≠ 数值最小：例如 "LR"（n=3）输出 2\n1\n3，而非 1\n2\n3（后者违反第二个方向 'R'：从 2→3 是 R，但第一个方向 L 要求 1→2，而 1→2 是 R，矛盾）；
- 方向串长度恒为 n−1，输出必须恰好 n 行，每行一个 1~n 的不同整数；
- 在 Kattis 平台，Python 的 input() 较慢，务必使用 sys.stdin；若本地测试，可加 sys.setrecursionlimit()（本题无需递归）。
总结
解决此类构造题的核心是跳出模拟思维，抓住“方向约束 → 相邻大小关系 → 分段单调性 → 贪心填充”这一逻辑链。通过消除中间数据结构、利用内置 range 批量生成、以及精准的指针扫描，可将原本 O(n²) 的朴素分组法优化至严格的 O(n)，轻松通过 2×10⁵ 规模的时限。记住：在算法竞赛中，I/O 效率与算法复杂度同等重要。
