1824. 钻石收藏家(双指针模板)
本文最后更新于 910 天前,其中的信息可能已经有所发展或是发生改变。

1824. 钻石收藏家(双指针模板)

原题链接

奶牛贝茜非常喜欢闪闪发光的东西,她会在业余时间开采钻石。

她收藏了 N 颗大小不等的钻石,她想将其中的一些摆放在牛棚的展示柜当中。

为了使展示柜中的钻石尺寸大小相似,她不会将两颗尺寸大小相差超过 K 的钻石同时放在柜子中(刚好相差 K,则没有问题)。

给定 K,请帮助贝茜计算在展示柜中最多可以摆放多少颗钻石。

输入格式

第一行包含两个整数 N,K。

接下来 N 行,每行包含一个整数,表示一颗钻石的尺寸。

输出格式

输出贝茜可以在展示柜中展示的钻石最大数量。

数据范围

1≤N≤1000,
0≤K≤100000,
钻石的尺寸范围 [1,10000]

输入样例:

5 3
1
6
4
3
1

输出样例:

4

分析

  • 要求放入钻石差值不超过k的条件下使得放入钻石数量最多

    等价于:对于一段数列,求子序列中的任意两数之差最大不超过k的最长子序列

  • 将数列排序使其单调,枚举i为右端点,j为左端点,数组名为a

  • a[i]a[j]的差值大于k,则需要向右移动j,直到a[i]a[j]的差值小于等于k

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;

int a[N];

int main(){
    int n,k,ans=0;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];  //读入并记录钻石尺寸
    sort(a,a+n);  //对钻石尺寸从小到大排序
    for(int i=0,j=0;i<n;i++){  //i枚举右端点
        while(a[i]-a[j]>k) j++;  //移动j的过程
        ans=max(ans,i-j+1);  //更新最长区间
    }
    cout<<ans<<endl;
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇