首页 > 试题广场 >

相差不超过k的最多数

[编程题]相差不超过k的最多数

热度指数：10727 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个包含 $n$ 个正整数的数组 $a_1,a_2,\dots ,a_n$ 。你需要从中选择若干个数（可以全部也可以一个都不选），使得在所选集合中任意两数的差的绝对值均不超过给定整数 $k$ 。
$\hspace{15pt}$ 请输出能够选出的元素个数的最大值。

【名词解释】
$\hspace{15pt}$ 若选出的元素集合为 $S$ ，则要求 $\max(S)-\min(S)\leqq k$ 。

输入描述:

第一行输入两个整数 。 
第二行输入  个整数 。

输出描述:

输出一个整数，表示满足条件的最多可选元素数量。

示例1

输入

5 3
2 1 5 3 2

输出

说明

选取元素集合  满足最大值与最小值之差为 ，且无法再加入 。

算法知识视频讲解

Python 3

略略哩

n,k=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()

max_len=0
start=0
for end in range(n):
    while nums[end]-nums[start]>k:
        start +=1
    max_len=max(max_len,end-start+1)
print(max_len)

发表于 2025-03-17 20:39:20 回复(0)

Python 3

.黑色.

def func(n, arr, k):
    
    arr = sorted(arr)
    ans = 0
    l = r = 0
    while r < n:
        if arr[r] - arr[l] <= k:
            ans = max(ans, r - l + 1)
        else:
            l += 1
        r += 1
    return ans
    


if __name__ == "__main__":
    
    n, k = [int(x) for x in input().split()]
    arr = [int(x) for x in input().split()]
    
    ans = func(n, arr, k)
    print(ans)

发表于 2022-03-28 09:41:19 回复(0)