相差不超过k的最多数

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

热度指数：6325 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过 $k$ 。问最多能选择多少个数？

输入描述:

第一行输入两个正整数 和。
第二行输入  个正整数，用空格隔开，表示这个数组。

输出描述:

一个正整数，代表能选的最多数量。
数据范围：

示例1

输入

5 3
2 1 5 3 2

输出

说明

显然，1和5不能同时选。所以最多只能选4个数。

算法知识视频讲解

小谷围做题家

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)