差距管理

[牛客链接](https://www.nowcoder.com/practice/4e23503c05634bd5be2c98fba4b91e3b)

思路

贪心。

要把连续下标的物品分成尽可能少的组，且每组内最大值与最小值之差不超过 $d$ 。既然组必须是连续区间，那最优策略就是每一组尽量往右延伸——只要加入下一个物品后组内极差仍 $\leq d$ ，就继续扩展；一旦超出，就在这里断开，开始新的一组。

具体做法：从左到右扫描，维护当前组的 $\min$ 和 $\max$ 。对于新元素 $a_i$ ：

若 $\max(\text{mx}, a_i) - \min(\text{mn}, a_i) \leq d$ ，则把 $a_i$ 纳入当前组，更新 $\text{mn}$ 和 $\text{mx}$ 。
否则，答案加 $1$ ，以 $a_i$ 作为新一组的起点，重置 $\text{mn} = \text{mx} = a_i$ 。

为什么贪心正确？ 假设某个最优解在位置 $j$ 断开了一组，但贪心策略还没有断开（即贪心组更长）。将最优解中 $j$ 之后的部分推迟到贪心的断点再分割，不会增加组数——因为组更长只是把后面的元素"提前消化"了，后续需要的组数不会更多。因此贪心的组数 $\leq$ 最优解的组数。

以样例 1 为例： $a = [1, 3, 1, 4]$ ， $d = 1$ 。

组 1 从 $a_0=1$ 开始；加入 $a_1=3$ 时极差 $= 2 > 1$ ，断开。
组 2 从 $a_1=3$ 开始；加入 $a_2=1$ 时极差 $= 2 > 1$ ，断开。
组 3 从 $a_2=1$ 开始；加入 $a_3=4$ 时极差 $= 3 > 1$ ，断开。
组 4 只有 $a_3=4$ 。共 4 组。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long d;
    scanf("%d%lld", &n, &d);
    vector<long long> a(n);
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    int ans = 1;
    long long mn = a[0], mx = a[0];
    for(int i = 1; i < n; i++){
        long long nmn = min(mn, a[i]);
        long long nmx = max(mx, a[i]);
        if(nmx - nmn > d){
            ans++;
            mn = mx = a[i];
        } else {
            mn = nmn;
            mx = nmx;
        }
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long d = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
        int ans = 1;
        long mn = a[0], mx = a[0];
        for (int i = 1; i < n; i++) {
            long nmn = Math.min(mn, a[i]);
            long nmx = Math.max(mx, a[i]);
            if (nmx - nmn > d) {
                ans++;
                mn = mx = a[i];
            } else {
                mn = nmn;
                mx = nmx;
            }
        }
        System.out.println(ans);
    }
}

复杂度

时间复杂度： $O(n)$ ，单次遍历数组。
空间复杂度： $O(n)$ ，存储输入数组。