[NOIP 2016 提高组] 蚯蚓

GitHub跳转原题关系图返回列表

用全局增量抵消统一加 q，并以三个单调队列线性取当前最长蚯蚓。

OJ: luogu

题目 ID: P2827

难度:提高+/省选-

标签:单调队列偏移量模拟python

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

反复取最长蚯蚓切成两段，其余长度统一加 q，按指定间隔输出切割值和最终排名。

思路

把统一增长记为全局 offset，队列中只存“实际长度减 offset”。初始降序序列是一条队列；每次切出的两类长度各自也按生成顺序单调不增，形成另外两条队列。当前最大值只需比较三个队首。

第 i 秒新段不参与本秒的 q，存入时减去 i*q。完成后继续三路归并即可得到最终降序序列。

Python 知识

  • 两个 array("q") 紧凑容纳最多七百万个生成长度。
  • 头下标代替 pop(0)，避免移动数组。
  • max(range(3), key=candidates.__getitem__) 找三队列最大队首。

代码

python
import sys
from array import array


data = iter(map(int, sys.stdin.buffer.read().split()))
n, seconds, increase, numerator, denominator, interval = (next(data) for _ in range(6))
initial = sorted((next(data) for _ in range(n)), reverse=True)
first = array("q")
second = array("q")
heads = [0, 0, 0]
cut_output = []


def pop_maximum():
    candidates = (initial[heads[0]] if heads[0] < len(initial) else -10**30,
                  first[heads[1]] if heads[1] < len(first) else -10**30,
                  second[heads[2]] if heads[2] < len(second) else -10**30)
    queue = max(range(3), key=candidates.__getitem__)
    heads[queue] += 1
    return candidates[queue]


for current_second in range(1, seconds + 1):
    length = pop_maximum() + (current_second - 1) * increase
    if current_second % interval == 0:
        cut_output.append(str(length))
    left_part = length * numerator // denominator
    offset = current_second * increase
    first.append(left_part - offset)
    second.append(length - left_part - offset)

print(" ".join(cut_output))
final_output = []
offset = seconds * increase
for rank in range(1, n + seconds + 1):
    length = pop_maximum() + offset
    if rank % interval == 0:
        final_output.append(str(length))
print(" ".join(final_output))

复杂度

排序 O(nlog⁡n)O(n\log n)，之后时间 O(n+m)O(n+m)，空间 O(n+m)O(n+m)。

总结

“除新元素外全部统一增加”通常可以用全局懒偏移消去；再识别生成序列单调性，就无需大堆。