首页 > 试题广场 >

相差不超过k的最多数

[编程题]相差不超过k的最多数
  • 热度指数：9868 时间限制：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。

输入描述:
\hspace{15pt}第一行输入两个整数 n,k\left(1\leqq n\leqq 2\times10^{5},\ 1\leqq k\leqq 10^{9}\right)。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots ,a_n\left(1\leqq a_i\leqq 10^{9}\right)。


输出描述:
\hspace{15pt}输出一个整数，表示满足条件的最多可选元素数量。
示例1

输入

5 3
2 1 5 3 2

输出

4

说明

选取元素集合 \{1,2,2,3\} 满足最大值与最小值之差为 3，且无法再加入 5。
算法知识视频讲解
开通博客
头像 starry陆离
发表于 2022-08-24 22:17:13
👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟🏡个人主页：starry陆离 🍁每日推荐：牛客网-面试神器 『牛客|每日一题』相差不超过k的最多数 1.每日一题 原题链接——》戳我戳我：传送法阵 2.测试案例 5 3 2 1 5 3 2 4 说明： 显然，1和5不能同时选。所以最多只能选4 展开全文
去ta的博客 赞 (7) 回复(2) 收起
头像 万卡you
发表于 2022-11-10 19:25:16
#include<iostream> #include<algorithm> using namespace std; int main(){ int n,k; cin>>n>>k; int a[ 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 小菲柱
发表于 2022-04-19 12:48:01
#include <iostream> #include <algorithm> #include <vector> int main(int argc, char *argv[]) { int count, dist; std::vector<i 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 1eHz
发表于 2024-10-26 00:02:59
关键词：双指针 / 滑动窗口核心思想：使用滑动窗口算法通过动态调整窗口的大小，遍历所有符合条件的连续子序列，求得最大连续子序列的长度。解题步骤：排序：首先对数组进行排序，以方便后续检查相邻元素之间的差值是否满足条件。滑动窗口：使用滑动窗口技术来找到满足条件的最长子序列。这里使用两个指针 l（左指针） 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 lee23333
发表于 2022-05-23 20:17:25
import java.util.*; public class Main {     public static void main(String[] args) { 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 有胆量的柯基在学习
发表于 2025-08-03 17:09:36
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >& 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 东北大学小白
发表于 2023-08-16 21:37:54
#include <iostream> using namespace std; #include <vector> #include <algorithm> int main() { int n, k; while (cin >> 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 燕草如碧
发表于 2022-08-02 21:45:49
n,k = map(int,input().split()) lis = list(map(int,input().split())) list.sort(lis) left = 0#左指针 right = 0#右指针 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 燕草如碧
发表于 2022-08-02 21:45:50
n,k = map(int,input().split()) lis = list(map(int,input().split())) list.sort(lis) left = 0#左指针 right = 0#右指针 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 蚂蚁go
发表于 2024-03-10 19:38:11
#include <bits/stdc++.h> using namespace std; vector<long long> a; long long n,k; bool find(long long l,long long r) { if(abs(a[l]-a[ 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

双指针
来自：华为机试编程模拟题9
难度：
24条回答 2287浏览

热门推荐

通过挑战的用户

查看代码

相关试题

相差不超过k的最多数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号