首页 > 试题广场 >

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

输出

说明

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

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
    "os"
    "bufio"
    "sort"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var n,k int
    fmt.Scan(&n,&k)
    arr:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Fscan(in,&arr[i])
    }
    sort.Ints(arr)
    ans:=0
    for l,r:=0,0;r<len(arr);r++{
        for arr[r]-arr[l]>k{
            l++
        }
        if r-l+1>ans{
            ans=r-l+1
        }
    }
    fmt.Print(ans)
}

发表于 2023-02-10 01:27:56 回复(0)