首页 > 试题广场 >

相差不超过k的最多数

[编程题]相差不超过k的最多数
  • 热度指数:7164 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组,选择一些数,要求选择的数中任意两数差的绝对值不超过 k 。问最多能选择多少个数?

输入描述:
第一行输入两个正整数 nk
第二行输入 n 个正整数a_i,用空格隔开,表示这个数组。


输出描述:
一个正整数,代表能选的最多数量。
数据范围:

示例1

输入

5 3
2 1 5 3 2

输出

4

说明

显然,1和5不能同时选。所以最多只能选4个数。
#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)