1824-钻石收藏家双指针模板

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;
}