原题描述

题目背景

很感人很刀但这里就不放了。

题目描述

现在问题来了：天空可以理解为一条数轴，在这条数轴上分布着许多颗星星，对于每颗星星都有它的位置 X_i 和自身的亮度 B_i。而窗户所能看到的范围是一个给出的参数W，我们看到的星星也包括窗户边缘的星星。现在，要你求出调整窗户位置后能看到星星的亮度之和最大值。

输入格式

一行 N,W，分别代表星星的数量和窗户的宽度

余下 N 行，输入 X_i 和 B_i，代表星星的坐标和亮度

输出格式

一个数字，代表能看到星星的最大亮度和

样例 #1

样例输入 #1

6 3
1 2
2 4
3 8
4 4
5 2
1000 1

样例输出 #1

16

提示

样例说明：

对于 10\% 的数据，W=0（没有边缘）

对于 40\% 的数据，W = 1000

对于 100\% 的数据，1 ≤ N ≤ 100000，0 ≤ W ≤ 100000，1 ≤ X_i ≤ 100000，1 ≤ B_i ≤ 100

除 W=0 的情况外，W 均为 ≥ 3 的奇数

题目简述与初步分析思路

  简述一下题意其实就是给定一条数轴，然后求规定大小的区间内的最大和。根据以往的经验我们可以将数轴简化为数组，数组的下标的意义代表的是星星的坐标，值为对应的亮度。

注意：

 1.看清题意，输入的N是星星的数量而不是星星的最大坐标，最大坐标需要在读入时取

 2.本题的一个坑点，一个坐标不止有一个星星，所以读入时需要在原先的基础上加对应的亮度而不是覆盖

 3.数据中可能存在w = 0的情况，当w = 0则答案直接为0(窗户给你封死看你怎么留恋)

接下来可以用的方法就很多了，对于解决区间和的问题，我们可以用前缀和、滑动窗口、树状数组、线段树等等，因为篇幅原因在这里我将介绍两种方法：前缀和、滑动窗口，对于此题来讲基本就是两种方法的板子题，并且两种方法本身的实现难度也很小，受众面更广，利于这个问题的解决。

方法一：滑动窗口

  这个思想可能在很多题目里都有提及过，但其本质其实就是一个特殊的双指针。所以在分析这道题目中可以分以下几步：

  1.头指针与尾指针之间的最大相隔距离就是窗口宽度w，在读入时我们可以预先记录星星的最小坐标，即X_min

  2.初始情况下令头指针left与尾指针right都等于X_min即为长度为1的窗口

这么做对于初始将指针指向1来讲可以省一些时间的消耗，算是一个小的优化。

  3.定义一个变量cnt并初始为left与right指针共同指向的值，用于记录窗口内的和，每次先将指针向右滑动，cnt的值在原先的基础上加新扫描到的值，此时需要判断窗口的宽度是否在要求的范围内，即 right - left + 1 <= w是否成立，如果不成立则需要先将cnt的值减去左指针指向的值，并将左指针右移一个单位。

  4.每次指针进行移动后都需要对最终的答案ans进行比对更新，因为要求滑动窗口和的最大值，所以需要进行ans = max(ans,cnt)，对于本题来讲星星的亮度是一个非负数，所以当right与星星的最大坐标相等时，即可直接结束(后面窗口长度缩小只会出现cnt减小或不变，不会出现增加)。

文字描述起来可能有些枯燥，因此可以通过下图来帮助大家理解：

以上两张图模拟了程序在运行时的步骤，也是我们要实现的步骤，那么看了这么多的理论分析，接下来我们就将思路转化为代码，完成此题：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int arr[N];

int main() {
    int n,w;
    cin >> n >> w;
    int left,right;
    left = right = N;
    int maxn = 0;
    for(int i = 1;i<=n;i++){
        int x,b;
        scanf("%d %d",&x,&b);
        arr[x] += b;
        maxn = max(x,maxn);
        left = right = min(left,x);
    }
    int ans = 0;
    int cnt = 0;//窗口内值
    cnt = arr[left];
    while(right <= maxn && w){
        right++;
        cnt += arr[right];
        if(right - left + 1 > w){
            cnt -= arr[left];
            left++;
        }
        ans = max(cnt,ans);
    }
    cout << ans << endl;
    return 0;
}

方法二：前缀和

  前缀和的概念在我之前的文章中已经讲过了，原理就是先通过O(n)复杂度的方式得到前缀和数组，后续即可通过O(1)复杂度查询区间和，因为题目中给出的是一维数轴，所以我们构建前缀和数组也肯定是一维，一维前缀和的构建和查询的数学关系如下：

  构建部分就没什么好说的了，用普通方式进行构建即可，而查询步骤就需要注意，在本题中因为要得到区间和的最大值，所以我们需要将覆盖的区间全部遍历一遍，因此需要确定一下遍历的首末位置。很显然我们可以发现，全程我们其实只需要关注控制右边界的right变量，窗户的宽度为w，所以right的初始值则为w，与滑动窗口的尾条件相同，当right等于星星的最大坐标时，查询结束，所以我们只需要right从w遍历到maxn(最大坐标)不断查询宽度为w的区间和即可，在每次查询后将其值与最后的答案ans取最大值，一轮遍历后则可以达到我们想要的结果。因为程序的执行步骤与滑窗的步骤基本相同，所以我也不再举例，最后也放上前缀和解决本题的代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N];
long long s[N];

int main()
{
    int n, w;
    cin >> n >> w;
    int maxn = 0;
    for (int i = 1; i <= n; i++)
    {
        int x, b;
        scanf("%d %d", &x, &b);
        a[x] += b;
        maxn = max(maxn, x); // 最大坐标
    }

    for (int i = 1; i <= maxn; i++)
    {
        s[i] += s[i - 1] + a[i];
    }

    if(!w){
        cout << 0 << endl;
    }else{
        long long ans = 0;
        for(int right = w;right <= maxn;right++){
            ans = max(ans,s[right] - s[right - w]);
        }
        cout << ans << endl;
    }
    return 0;
}

总结

  在本章中我们用了两种的方法来解决此题，分别是滑动窗口以及前缀和，在解决后相信大家对这两种算法又有了更深的印象，算法的学习也需要不断的巩固、积累，这样才能更上一层楼。

  好了本期内容到这里就结束了，如果你认为该文章对你有一点点帮助，也请希望收藏我的主页或者关注微信公众号：ModCx，如果有什么疑问或者建议也可在微信公众号后台留言，你们的支持就是我的动力，让我们下期再见~