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会被计算)，然后取最大值即可。

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

贴代码~

#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;
}