[USACO16OPEN] 钻石收藏家 S

题目描述

奶牛贝茜非常喜欢闪闪发光的东西，她在业余时间养成了开采钻石的爱好！她收集了 $N$ 颗大小不一的钻石（$N \leq 50,000$），想要把其中一部分摆放在谷仓里的两个展示柜中。

贝茜希望同一个展示柜里的钻石大小尽可能相近，因此她规定：同一柜子里任意两颗钻石的大小差不能超过 $K$（大小差恰好等于 $K$ 时可以放在一起）。

给定 $K$ 的值，请你帮贝茜计算：两个展示柜最多能一起摆放多少颗钻石（两个柜子里的钻石无任何大小限制）。

输入格式

• 第一行：两个整数 $N$ 和 $K$（$0 \leq K \leq 1,000,000,000$）。
• 接下来 $N$ 行：每行一个整数，表示一颗钻石的大小。 所有大小均为正数，且不超过 $1,000,000,000$。

输出格式

• 输出一个正整数，表示两个展示柜最多能摆放的钻石总数。

输入样例 1：

7 3
10
5
1
12
9
5
14

输出样例 1：

5

提示

（暂无提示）

标签: P3143|动态规划 DP|贪心|2016|USACO|枚举|双指针 two-pointer

来源

P3143|[USACO16OPEN] Diamond Collector S