[USACO16OPEN] Diamond Collector S

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

排序后用双指针求每个起点的最长合法区间，再用后缀最优组合两个不相交展示柜。

OJ: luogu

题目 ID: P3143

难度:普及/提高-

标签:双指针后缀最值python

日期: 2026-07-16 18:25

目录

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

题意

把尽量多的钻石放进两个展示柜，每柜内部最大尺寸差不超过 KK。

思路

排序后，一个柜中的最优选择一定是连续区间。双指针求出每个左端 i 能延伸到的最远 right[i]。best_suffix[p] 保存从位置 p 开始可选的最长合法区间，枚举第一柜后把第二柜接在 right[i]+1 之后即可保证不重叠。

Python 知识

  • diamonds = sorted(data) 直接消费剩余整数迭代器。
  • 右指针只前进不后退，总计线性移动。
  • 逆序循环一行维护后缀最大长度。

代码

python
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n, limit = next(data), next(data)
diamonds = sorted(data)
right = [0] * n
j = 0
for i, smallest in enumerate(diamonds):
    j = max(j, i)
    while j + 1 < n and diamonds[j + 1] - smallest <= limit:
        j += 1
    right[i] = j

best_suffix = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    best_suffix[i] = max(best_suffix[i + 1], right[i] - i + 1)

print(max(right[i] - i + 1 + best_suffix[right[i] + 1] for i in range(n)))

复杂度

时间复杂度 O(nlog⁡n)O(n\log n)，空间复杂度 O(n)O(n)。

总结

两个不相交区间的组合常用“枚举第一段 + 后缀最优第二段”。