首页 > 试题广场 >

差距管理

[编程题]差距管理

有 $n$ 个物品，第 $i$ 个物品的价值为 $a_i$ 。现在要给这些物品分组，每一组必须是一个下标连续的区间。同时，每一组内的物品差距不能太大，即任意一组内物品的最大价值减去最小价值不能超过某个给定的常数 $k$ 。

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

第一行两个整数  ，表示物品的数量及给定的常数。

第二行  个整数  ，表示物品的价值。

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

示例1

输入

4 1
1 3 1 4

示例2

4 2
1 3 1 4

算法知识视频讲解

查看答案及解析

骆亮

动态维护区间最小值最大值，左端点更新（当最大值-最小值>k时）一次就是分割一次，最后res=分割次数+1

发表于 2025-07-26 00:35:54 回复(0)

approt

一般

发表于 2025-07-23 23:12:08 回复(0)

提交观点

贪心数组京东

难度：

2条回答 14收藏 239浏览

差距管理

扫一扫，把题目装进口袋