首页 > 试题广场 >

相差不超过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

输出

说明

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

算法知识视频讲解

人生有三乐

#include <stdio.h>

#include <stdlib.h>

int compare(const void* p1,const void *p2)

{

long t1=*(long int*)p1;

long t2=*(long int*)p2;

if (t1<t2) {

return -1;

}else if (t1>t2){

return 1;

}

return 0;

}

int main() {

int n;

long k; //要考虑10的9次方的情况啊

scanf("%d %ld",&n,&k);

long int array[n];

for (int i=0; i<n; i++) {

scanf("%ld",&array[i]);

}

//排序一下

qsort(array, n,sizeof(long int), compare);

int max_count = 1; // 至少有一个元素的子集

int j = 0; // 右指针

// 滑动窗口：i是左指针，j是右指针，遇到j走不动的情况，只需要让i向右走这样更快，因为这样也是在缩小它们之间的差值

for (int i = 0; i < n; i++) {

// 关键：j不需要重置，因为数组已排序

// 当array[j] - array[i] <= k时，继续扩展右边界

while (j < n && array[j] - array[i] <= k) {

j++;

}

// 当前窗口大小是 j - i

if (j - i > max_count) {

max_count = j - i;

}

printf("%d",max_count);

return 0;

}

发表于 2025-10-19 15:46:38 回复(0)

cs小白_

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a,const void* b){
    return (*(int*)a-*(int*)b);
}
int myselect(int* a,int n,int k){
    qsort(a, n, sizeof(int), compare);
    int max=0,l=0,r=0;
    for (r=0; r<n; r++) {
         while (a[r]-a[l]>k) {
            l++;
         }
         int cur_count=r-l+1;
         if (cur_count>max) {
              max=cur_count;
         }
    }
    return max;
}
int main() {
    int m,n;
    scanf("%d %d", &m, &n);
    int* a=(int*)malloc(sizeof(int)*m);
    for (int i=0; i<m; i++) {
        scanf("%d", &a[i]);
    }
    int res=myselect(a, m, n);
    printf("%d", res);

    return 0;
}

发表于 2024-11-29 16:18:25 回复(0)