懒惰的牛

题目链接

这是一个炎热的夏日。

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

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

第 i 片草地中包含 $g_i$ 单位的青草，位置坐标为 $x_i$。

不同草地的位置不同。

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

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

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

输入格式

第一行包含两个整数 N 和 K。

接下来 N 行，每行描述一片草地，包含两个整数 $g_i$ 和 $x_i$。

输出格式

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

数据范围

1≤N≤100000,

1≤ $g_i$ ≤10000,

0≤ $x_i$ ≤1000000,

1≤K≤2×1000000

输入样例:

4 3
4 7
10 15
2 2
5 1

输出样例：

11

样例解释

最佳初始位置选择为 x=4，可以吃到 x=1,x=2,x=7 处的青草。

思路

解法一：

使用滑动窗口法求解。

  1. 按照坐标排序；
  2. 移动右边界，累加草的数量；
  3. 收缩窗口，控制窗口大小；
  4. 取sum最大值。
#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;

int n, m;
PII q[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d%d", &q[i].y, &q[i].x); //草的数量及曹的坐标

    sort(q, q + n); // 排序
    
    int res = 0, sum = 0;
    for (int i = 0, j= 0; i < n; i++) { // 移动右边界
        sum += q[i].y;
        while (q[i].x - q[j].x > m * 2) { //窗口收缩
            sum -= q[j ++].y;
        }
        res = max(res, sum);
    }
    printf("%d\n",res);
    return 0;
}