原题描述
题目背景
很感人很刀但这里就不放了。
题目描述
现在问题来了:天空可以理解为一条数轴,在这条数轴上分布着许多颗星星,对于每颗星星都有它的位置 Xi 和自身的亮度 Bi。而窗户所能看到的范围是一个给出的参数W,我们看到的星星也包括窗户边缘的星星。现在,要你求出调整窗户位置后能看到星星的亮度之和最大值。
输入格式
一行 N,W,分别代表星星的数量和窗户的宽度
余下 N 行,输入 Xi 和 Bi,代表星星的坐标和亮度
输出格式
一个数字,代表能看到星星的最大亮度和
样例 #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 ≤ Xi ≤ 100000,1 ≤ Bi ≤ 100
除 W=0 的情况外,W 均为 ≥ 3 的奇数
题目简述与初步分析思路
简述一下题意其实就是给定一条数轴,然后求规定大小的区间内的最大和。根据以往的经验我们可以将数轴简化为数组,数组的下标的意义代表的是星星的坐标,值为对应的亮度。
注意:
1.看清题意,输入的N是星星的数量而不是星星的最大坐标,最大坐标需要在读入时取
2.本题的一个坑点,一个坐标不止有一个星星,所以读入时需要在原先的基础上加对应的亮度而不是覆盖
3.数据中可能存在w = 0的情况,当w = 0则答案直接为0(窗户给你封死看你怎么留恋)
接下来可以用的方法就很多了,对于解决区间和的问题,我们可以用前缀和、滑动窗口、树状数组、线段树等等,因为篇幅原因在这里我将介绍两种方法:前缀和、滑动窗口,对于此题来讲基本就是两种方法的板子题,并且两种方法本身的实现难度也很小,受众面更广,利于这个问题的解决。
方法一:滑动窗口
这个思想可能在很多题目里都有提及过,但其本质其实就是一个特殊的双指针。所以在分析这道题目中可以分以下几步:
1.头指针与尾指针之间的最大相隔距离就是窗口宽度w,在读入时我们可以预先记录星星的最小坐标,即Xmin
2.初始情况下令头指针left与尾指针right都等于Xmin即为长度为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,如果有什么疑问或者建议也可在微信公众号后台留言,你们的支持就是我的动力,让我们下期再见~
R102112904人win节打卡
查看图片