懒惰的牛

题目

链接：1922. 懒惰的牛 - AcWing题库

这是一个炎热的夏日。

懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置，以便可以在短距离内尽可能多地吃到美味的草。

贝茜所在的田野中共有 N 片草地，我们可以将田野视作一个一维数轴。

第 i 片草地中包含 gi 单位的青草，位置坐标为 xi。

不同草地的位置不同。

贝茜想选取田野中的某个点作为她的初始位置（可能是某片草地所在的点）。

只有一片草地与她的初始位置的距离不超过 K 时，贝茜才能吃到那片草地上的草。

如果贝茜选择最佳初始位置，请确定她可以吃到的青草最大数量。

代码

import java.util.*;


public class Main {
    static int N = 1000010;
    static int n, k, len = 0;
    static int[] a = new int[N];
    static int[] sum = new int[N];
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        k = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            int g = inScanner.nextInt();
            int x = inScanner.nextInt();
            a[x + 1] = g;
            len = Math.max(x + 1, len);
        }
        inScanner.close();
        sum[0] = 0;
        for(int i = 1; i <= len; i ++)
            sum[i] = sum[i - 1] + a[i];
        int ans = 0;
        for(int i = 1; i <= len; i ++)
        {
            int l = Math.max(0, i - k - 1);
            int r = Math.min(len, i + k);
            ans = Math.max(ans, sum[r] - sum[l]);
        }
        System.out.println(ans);
    }
}
/*
4 3
4 7
10 15
2 2
5 1
*/