首页 > 试题广场 >

相差不超过k的最多数

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

热度指数：8983 时间限制：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

输出

说明

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

算法知识视频讲解

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)