【贪心5】物品分组

题面简述

给定 n 个物品，每个物品有一个价值 a_i，我们需要将这些物品分组，每组必须是下标连续的区间。题目要求每组内物品的最大价值和最小价值之差不能超过一个给定的常数 k，问最少需要分成多少组。

解题思路

思路概述

这个问题实际上可以通过 贪心算法 来解决。我们从左到右遍历物品，并且尝试在不违反条件（最大值与最小值的差不超过 k）的情况下尽量将物品分配到一个组内。如果当前物品无法与前面的物品在一个组内满足条件，就开始新的组。

本题为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)$，表示物品的价值。

输出描述

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

样例1

输入

4 1
1 3 1 4

输出

4

说明

样例2

输入

4 2
1 3 1 4

输出

2

说明