【贪心5】物品分组

题面简述

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

解题思路

思路概述

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

贪心策略：

1. 初始化分组数量为 1（至少有一组）。
2. 使用两个变量 max_val 和 min_val 来记录当前组内的最大值和最小值。
3. 从左到右遍历物品，判断当前物品是否能够加入到当前组：
   • 如果加入后，当前组的最大值和最小值之差仍然不超过 k，则将当前物品加入当前组。
   • 否则，说明需要开始一个新的组，更新分组数量，并且重新设置当前组的最大值和最小值。
4. 继续遍历，直到所有物品分组完成。

复杂度分析

• 时间复杂度：O(n)，因为我们只需要遍历一遍物品列表。
• 空间复杂度：O(1)，除了常数空间外，不需要额外的空间。

Python代码

def min_groups(n, k, a):
    # 初始化分组数和当前组的最大最小值
    group_count = 1
    min_val = a[0]
    max_val = a[0]

    # 从第二个物品开始遍历
    for i in range(1, n):
        # 如果当前物品加入组后，最大值和最小值之差超过k，则需要分新的一组
        if a[i] - min_val > k or max_val - a[i] > k:
            group_count += 1
            min_val = a[i]  # 新组的最小值
            max_val = a[i]  # 新组的最大值
        else:
            # 更新当前组的最大值和最小值
            min_val = min(min_val, a[i])
            max_val = max(max_val, a[i])

    return group_count

# 输入处理
n, k = map(int, input().split())
a = list(map(int, input().split()))

# 输出结果
print(min_groups(n, k, a))

Java代码

import java.util.Scanner;

public class Main {

    public static int minGroups(int n, int k, int[] a) {
        // 初始化分组数和当前组的最大最小值
        int groupCount = 1;
        int minVal = a[0];
        int maxVal = a[0];

        // 从第二个物品开始遍历
        for (int i = 1; i < n; i++) {
            // 如果当前物品加入组后，最大值和最小值之差超过k，则需要分新的一组
            if (a[i] - minVal > k || maxVal - a[i] > k) {
                groupCount++;
                minVal = a[i];  // 新组的最小值
                maxVal = a[i];  // 新组的最大值
            } else {
                // 更新当前组的最大值和最小值
                minVal = Math.min(minVal, a[i]);
                maxVal = Math.max(maxVal, a[i]);
            }
        }

        return groupCount;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入处理
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        // 输出结果
        System.out.println(minGroups(n, k, a));
    }
}

C++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minGroups(int n, int k, vector<int>& a) {
    // 初始化分组数和当前组的最大最小值
    int groupCount = 1;
    int minVal = a[0];
    int maxVal = a[0];

    // 从第二个物品开始遍历
    for (int i = 1; i < n; i++) {
        // 如果当前物品加入组后，最大值和最小值之差超过k，则需要分新的一组
        if (a[i] - minVal > k || maxVal - a[i] > k) {
            groupCount++;
            minVal = a[i];  // 新组的最小值
            maxVal = a[i];  // 新组的最大值
        } else {
            // 更新当前组的最大值和最小值
            minVal = min(minVal, a[i]);
            maxVal = max(maxVal, a[i]);
        }
    }

    return groupCount;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 输出结果
    cout << minGroups(n, k, a) << endl;

    return 0;
}

本题为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

说明