BISHI118　相差不超过k的最多数¶

中等通过率 30.81%python3样例通过牛客 AC双指针

牛客原题　源码

讲解章节：桶计数与离散化、双指针与滑动窗口

一句话

选一个子集使 max-min <= k，求最大元素个数。

解题思路¶

这题考什么¶

「集合中任意两数之差 <= k」只和 max、min 有关，与选取顺序无关，所以排序后答案一定是一段连续区间（排序后的下标区间）。问题化为：排序后找最长的区间 [l, r] 满足 a[r] - a[l] <= k。

排序后 a 单调不减 => 固定 r 时，合法的最小 l 随 r 单调不减 => 双指针 O(n)。

数据规模与复杂度¶

n <= 2e5。排序 O(n log n)（Timsort，C 层），双指针 O(n)。朴素枚举两端是 O(n^2) = 4e10，必挂。

坑在哪¶

必须先排序——不排序直接对原数组做滑动窗口是错的，因为题目选的是子集不是子段；
相等元素要能全部选进来（用 <= 判断，不是 <）；
「可以一个都不选」是干扰项：n >= 1 时单个元素总是合法，答案至少是 1；
a_i、k 都到 1e9，C++ 里做差不会溢出但要小心，Python 无此问题。

参考实现¶

solutions/BISHI118.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    # 排序把「任选子集」变成「取一段连续区间」，这是本题唯一的转化步骤
    a = sorted(map(int, data[2:2 + n]))
    l = 0                                    # 窗口左端，全程只增不减
    best = 0
    for r in range(n):
        x = a[r]                             # 排序后 a[r] 就是窗口最大值
        # a[l] 是窗口最小值；差超过 k 就把左端往右收，直到重新合法
        while x - a[l] > k:                  # 左端右移到合法为止（总共只走 n 步）
            l += 1
        if r - l + 1 > best:                 # 此刻 [l, r] 是以 r 结尾的最长合法区间
            best = r - l + 1
    sys.stdout.write("%d\n" % best)


main()

BISHI118 相差不超过k的最多数¶