题解 P3353 【在你窗外闪耀的星星】

P3353 题解


在做P1502 窗口的星星时偶然发现了这道题,看到这题的名字以后好奇心大增,就决定点进去看看。。。

本来看到这只是道黄题没打算做,直到这题超级长的题面让我想起了我在学校的【已编辑】,于是决定A之以明志


题目大意

天空中有$n$颗星星,求宽度为$W$的窗户(高度无限)最多能圈住亮度为多少的星星。

仔细分析后,我们发现我们可以将天空视作一个数轴,将$x$坐标相等的星星亮度累加在一起(反正$y$坐标没用),然后依次统计出每个长度为$W$的区间和,最后求最大值就可以了。


暴力算法

由上面的题目大意,可以十分直接地得到一个暴力算法——由$W$到最大的$x$坐标循环枚举,每次用循环求出$i-w$到$i$的区间和,然后取最大值

期望得分:(想要期望得分?这玩意估计也只能对拍用)


正解——前缀和

首先,我们要介绍一下前缀和

前缀和,指在一个序列中由序列起始位置到当前位置的和,如
$$Sum_i=A_1+A_2+A_3+A_4+···+A_i$$

前缀和的作用是 $O(1)$ 地维护静态区间和,原理为:
$$Sum_i=A_1+A_2+A_3+A_4+···+A_i$$

$$Sum_j=A_1+A_2+A_3+A_4+···+A_j,j>i$$

则$Sum_j$一定包含$Sum_i$,即
$$Sum_j=A_1+A_2+A_3+A_4+···+A_i+A_(i+1_)+···+A_j$$


$$Sum_j-Sum_i=(A_1+A_2+A_3+A_4+···+A_i+A_(i+1_)+···+A_j)$$
$$-(A_1+A_2+A_3+A_4+···+A_i)=A_(i+1_)+A_(i+2_)+···+A_j$$
所以
$$ A_(i+1_)+A_(i+2_)+···+A_j$$
即为i到j的区间和

由此,我们可以得出最后的思路——在输入完成后,$O(n)$ 预处理出前缀和数组sum,然后对每个区间和操作,返回sum[i]-sum[i-w] (因为只有i-w+1 ~ i会被计算),然后取最大值即可。

至此,问题得到完美解决。完结撒花

贴代码~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<iostream>
#include<algorithm>
using namespace std;
const int maxw=100005;
long long n,w,x,b;
long long maxx=0,ans=0;
long long br[maxw];//亮度数组
long long sum[maxw];//前缀和数组
int main(int argc, char const *argv[]) {
ios::sync_with_stdio(false);//流式I/O速度优化
cin.tie(0);//流式I/O速度优化
cin>>n>>w;
for(int i=1;i<=n;i++)
{
cin>>x>>b;
br[x]+=b;//向指定的X坐标累加亮度
maxx=max(maxx,x);//更新x的最大值
}
for(int i=1;i<=maxx;i++) sum[i]=sum[i-1]+br[i];//递推处理前缀和数组
for(int i=w;i<=maxx;i++)
{
ans=max(ans,sum[i]-sum[i-w]);//区间和与取最大值
}
cout<<ans<<endl;
return 0;
}
文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/题解-P3353-【在你窗外闪耀的星星】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏