- 题目
- 题解(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; }
