#P3143. [USACO16OPEN] Diamond Collector S

    ID: 2182 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>贪心2016USACO枚举,暴力双指针,尺取法,two-pointer

[USACO16OPEN] Diamond Collector S

Description

奶牛 Bessie 一直喜欢闪闪发光的物体,她最近在业余时间开始了一项爱好——挖掘钻石!她收集了 NN 颗大小各不相同的钻石(N50,000N \leq 50,000),并希望将它们中的一部分放在谷仓里的两个展示柜中展示。

由于 Bessie 希望每个展示柜中的钻石大小相对接近,她决定如果两颗钻石的大小相差超过 KK,就不能将它们放在同一个展示柜中(如果两颗钻石的大小相差恰好为 KK,则可以将它们一起展示在同一个展示柜中)。给定 KK,请帮助 Bessie 确定她可以在两个展示柜中一起展示的最大钻石数量。

Input Format

输入文件的第一行包含 NNKK0K1090 \leq K \leq 10^9)。

接下来的 NN 行每行包含一个整数,表示一颗钻石的大小。所有钻石的大小均为正数且不超过 10910^9

Output Format

输出一个正整数,表示 Bessie 可以在两个展示柜中一起展示的最大钻石数量。

7 3
10
5
1
12
9
5
14
5