P14350.【贪心5】物品分组

1000ms

Difficulty: 5

算法与标签>贪心算法

本题为2024年9月21日京东机考原题

京东机考的介绍点击这里

题目内容

有 $n$ 个物品，第 $i$ 个物品的价值为 $a_i$ 。

现在要给这些物品分组，每一组必须是一个下标连续的区间。

同时，每一组内的物品差距不能太大，即任意一组内物品的最大价值减去最小价值不能超过某个给定的常数 $k$ 。

给定这些物品，请问最少要分几组?

第一行两个整数 $n,k(1 ≤n≤ 10^5 ,0 ≤k≤ 10^9)$ ，表示物品的数量及给定的常数。

第二行 $n$ 个整数 $a (0 ≤ a_i ≤ 10^9)$ ，表示物品的价值。

输出一行一个整数，表示最少的分组数。

输入

4 1
1 3 1 4

输出

说明

输入

4 2
1 3 1 4

输出

说明

输入

预期输出（选填）