1 条题解

  • 0
    @ 2025-10-14 15:36:24

    核心思路

    • 相邻且高度差 ≤ K 的草堆可以交换,形成连通块
    • 在连通块内草堆可以任意重排
    • 从左到右贪心,每次选择当前能放到该位置的最小值

    算法步骤

    1. 维护数据结构(平衡树/堆)存储当前可用的草堆
    2. 确定交换范围
      • 对于当前位置 i,找到它能与哪些位置的草堆交换
      • 这需要满足区间内所有相邻草堆高度差 ≤ K
    3. 贪心选择
      • 从可用草堆中选出最小的能放到当前位置的
      • 将该草堆放到当前位置,并从数据结构中移除
    4. 更新可用草堆
      • 当新的草堆进入交换范围时,加入数据结构

    复杂度:O(N log N)

    关键点:用单调栈或线段树快速判断两个草堆是否能通过一系列交换相遇,然后用贪心构造字典序最小序列。

    • 1

    「USACO 2022.1 Platinum」Minimizing Haybales

    信息

    ID
    3120
    时间
    3500ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    13
    已通过
    1
    上传者