牛客网真题-76-路由器-美团MT49

差分数组，差分数组就是找一个基准，D[i]=A[i]-A[i-1]表示第i个元素比前一个元素大D[i],那么从0到i的累加和就是D[i]比第0项大多少。
如果使得第0项为0，然后在经过一系列变化，通过再与第0项对比就知道现在变化了多少，第0项在变化过程前后没有产生变化，因为它是基准。
``` java
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int cnt = 0;
        int[] router = new int[n];
        for(int i = 0; i < n; i++){

            int signal = scanner.nextInt();
            int start = Math.max(i - signal, 0);//router[0]=router[0]-router[-1],router[-1]=0没有具体表示出来;
            router[start]++;
            if(signal + i + 1 < n){
                router[signal + i + 1]--;
            }
        }
        int sum = 0;
        for(int i = 0; i < router.length; i++){
            sum += router[i];
            if(sum >= k){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

```