1 条题解
-
0
核心思路:
- 相邻且高度差 ≤ K 的草堆可以交换,形成连通块
- 在连通块内草堆可以任意重排
- 从左到右贪心,每次选择当前能放到该位置的最小值
算法步骤:
- 维护数据结构(平衡树/堆)存储当前可用的草堆
- 确定交换范围:
- 对于当前位置 i,找到它能与哪些位置的草堆交换
- 这需要满足区间内所有相邻草堆高度差 ≤ K
- 贪心选择:
- 从可用草堆中选出最小的能放到当前位置的
- 将该草堆放到当前位置,并从数据结构中移除
- 更新可用草堆:
- 当新的草堆进入交换范围时,加入数据结构
复杂度:O(N log N)
关键点:用单调栈或线段树快速判断两个草堆是否能通过一系列交换相遇,然后用贪心构造字典序最小序列。
- 1
信息
- ID
- 3120
- 时间
- 3500ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 13
- 已通过
- 1
- 上传者