1 条题解

  • 0
    @ 2026-11-15 21:16:44

    题目分析

    B. 书架平衡

    可以发现 hh 满足单调性(hh 越大花费越少),我们可以二分 hh,然后 O(n)O(n) 检查是不是符合条件。

    检查实现:

    • 对于每一个位置 ii,需要进行的消除次数是 ui+di−hu_i + d_i - h。
    • 为了满足 ∣ui−ui+1∣≤x|u_i - u_{i + 1}| \le x 的条件,ui+1u_{i + 1} 可行的范围是 [min⁡ui−x,max⁡ui+x][\min u_i - x, \max u_i + x]。
    • $\min u_i = \max(0, u_i - (u_i + d_i - h)) = \max (0, h - d_i)$ , max⁡ui=ui\max u_i = u_i。

    时间复杂度: O(nlog⁡(ui+di))O(n \log(u_i + d_i))。

    • 1

    信息

    ID
    198
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者