HJ181 相差不超过k的最多数

• 题目
• 题解(53)
• 讨论(29)
• 排行

中等 通过率：29.67% 时间限制：1秒 空间限制：256M

知识点双指针

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

给定一个包含 nn 个正整数的数组 a1,a2,…,ana1​,a2​,…,an​。你需要从中选择若干个数（可以全部也可以一个都不选），使得在所选集合中任意两数的差的绝对值均不超过给定整数 kk。
请输出能够选出的元素个数的最大值。

【名词解释】
若选出的元素集合为 SS，则要求 max⁡(S)−min⁡(S)≦kmax(S)−min(S)≦k。

输入描述：

第一行输入两个整数 n,k(1≦n≦2×105, 1≦k≦109)n,k(1≦n≦2×105, 1≦k≦109)。
第二行输入 nn 个整数 a1,a2,…,an(1≦ai≦109)a1​,a2​,…,an​(1≦ai​≦109)。

输出描述：

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

示例1

输入：

5 3 2 1 5 3 2

复制输出：

4

复制说明：

选取元素集合 {1,2,2,3}{1,2,2,3} 满足最大值与最小值之差为 33，且无法再加入 55。

#include<iostream> #include<algorithm> using namespace std; int main(){ int n,k; cin>>n>>k; int a[n]; for(int i=0;i<n;i++)cin>>a[i]; sort(a,a+n); int l=0,r=1; int max=1; while(r<n){ if(a[r]-a[l]<=k){ if(max<r-l+1)max=r-l+1; r++; } else if(l<r){ l++; } } cout<<max; }