1 条题解

  • 0
    @ 2026-11-15 21:38:37

    题目分析

    D. 书架上的古籍

    1. 首先我们假定一个操作顺序 p1,2,⋯ ,np_{1, 2, \cdots, n}。
    2. 我们可以发现每一个古籍最多被操作两次。
      • 如果前面的书架还没有达到最大值,移动到前面的书架,总共操作 11 次。
      • 否则,先移动到最后一个书架,最后再在清空最后一个书架时前移,总共操作 22 次。
    3. 先清空所有 ai≤bia_i \le b_i 的书架,再清空 ai>bia_i > b_i 显然是最优的。当 (ax≤bx)=(ay≤by)(a_x \le b_x) = (a_y \le b_y) 时,如果位于 yy, xx 两个位置的书架要交换位置,必须满足 $\max(a_x, a_x + (a_y - b_x)) \le \max(a_y, a_y + (a_x - b_y))$,即让交换后要操作 22 次的书架数量减小。
      • 当 ai≤bia_i \le b_i 即 ai−bi≤0a_i - b_i \le 0 时,所以 $\max(a_x, a_x + (a_y - b_x)) \le \max(a_y, a_y + (a_x - b_y))$ 等价于 ax≤aya_x \le a_y。
      • 当 ai>bia_i > b_i 即 ai−bi>0a_i - b_i > 0 时,所以 $\max(a_x, a_x + (a_y - b_x)) \le \max(a_y, a_y + (a_x - b_y))$ 等价于 bx>byb_x > b_y。
    4. 统计答案时只需要记录需要进行两次操作的书架数量再加上所有书架的数量 ∑a\sum a。
    5. 统计两次操作的书架数量方法为,枚举 1≤i≤n1 \le i \le n,将第 pip_i 个书架作为最后清空的书架,需要进行 22 次操作的书架数量为
      • [1,i−1][1, i - 1] 每一堆书架清空操作时,需要进行 22 次操作的书架的数量以及
      • 删除第 ii 个书架以后,剩余书架按顺序消除时,消除到每一堆时需要进行 22 次操作的书架的数量的最大值。
    6. 维护一个前缀 $\text{pre}_i = \max(\text{pre}_{i - 1}, \text{prea}_i - \text{preb}_{i - 1})$,以及一个后缀 $\text{suf}_i = \max (\text{suf}_{i + 1}, \text{prea}_{i + 1} - \text{preb}_i)$。当 ∑b−bi≥∑a\sum b - b_i \ge \sum a 时,$\text{ans} = \sum a + \min_{i = 1}^{n}\max(\text{pre}_i, \text{suf}_i - (a_{p_i} - b_{p_i}), 0)$。
    • 1

    信息

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