洛谷P3353 在你窗外闪耀的星星 题解

题目链接：P3353 在你窗外闪耀的星星

题意：

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

输入格式：

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

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

输出格式：

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

数据范围：

对于 \(100\%\) 的数据，\(1 \leq N\leq 10 ^ 5\)，\(0 \leq W\leq 10 ^ 5\)，\(1 \leq X_i\leq 10 ^ 5\)，\(1\leq B_i\leq 100\)。

除 \(W=0\) 的情况外，\(W\) 均为 \(\geq 3\) 的奇数。

把所有的点按 \(x\) 排序，然后维护一个指针 \(p\) 跟着 \(i\) 跑就完事了

时间复杂度 \(\mathcal{O}(n \log n)\) ，空间复杂度 \(\mathcal{O}(n)\) ，题目里其他的限制意义不明。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int res, p = 1, sum[N];
struct node { int x, v; } a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].v;
    sort(a + 1, a + 1 + n, [](node a, node b) { return a.x < b.x; });
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].v;
    for(int i = 1; i <= n; i++) {
        while(p <= n && a[i].x - a[p].x >= m) ++p;
        up(res, sum[i] - sum[p - 1]);
    }
    cout << res << '\n';
    return 0;
}

---

题外话：

油盐不进。

\(\color{white}{\tt 这里没有隐藏文字。}\)

还是贴一下题目背景吧，真是够中二的（

很遗憾，本人没有这种中二的时期，因此不是很能理解。。。

飞逝的时光不会模糊我对你的记忆。难以相信从我第一次见到你以来已经过去了 3 年。我仍然还生动地记得，3 年前，在美丽的集美中学，从我看到你微笑着走出教室，你将头向后仰，柔和的晚霞照耀着你玫瑰色的脸颊。我明白，我已经沉醉于你了。之后，经过几个月的观察和窥探，你的优雅与智慧，你对待生活的态度和你对未来的愿望深切地在我心中留下了印象。你是迷人的阳光女孩，我总是梦想着与你分享余生。唉，实际上你远远超过了我最疯狂的梦想。我不知道如何桥起我与你之间的鸿沟。所以我没有任何计划，仅仅只是等待，等待一个适当的机会到来。直到现在，毕业的到来，我意识到我是个傻瓜，我应该创造机会并且抓住它而不只是等待。

这些日子里，我和我的朋友、室友、同学一个接一个地分开。我仍无法相信，在挥手之后，这些熟悉的面孔很快就会从我们的生活中消失，仅仅留下回忆。我明天就将离开学校。你已经计划远走高飞，追求你的未来，实现你的梦想。如果没有命运，也许我们不会再次相遇。所以今晚，我正在你的宿舍楼下徘徊，希望能偶然遇见你。但矛盾的是，你的美貌一定会使我心跳加速，我笨拙的舌头也许无法吐出一个字。我不记得我曾多少次经过你的宿舍楼，每次都希望看到你出现在阳台上或是窗台上。我不记得这个想法曾多少次在我的脑海中涌出：打电话叫她一起吃晚饭或是聊聊天。但每次，考虑到你的优秀和我的平凡，胆怯的优势超越勇气驱使我静静地离开。

毕业，意味着中学生活的终结。这些光荣与浪漫的时代结束。你可爱的微笑是我原来努力学习的动力，这单相思的爱情会被密封，作为一个我心灵深处的记忆。毕业，也意味着新生活的开始，一个到达光明未来的足迹。我真希望你在国外天天开心，一切顺利。同时，我将努力从幼稚中走出来，变得更加成熟。我的理想将是在现实中追求我的爱与幸福，我永远不会放弃。

再见了，我的公主！

如果有一天，在某个天涯海角，我们有机会相聚，即使是白发苍苍的男人和女人，在那个时候，我希望我们可以成为好朋友来自豪地分享这个记忆，重温年轻快乐的激情。如果这个机会永远没有到来，我希望我是天空中的星星，在你的窗外闪烁。远远地保佑着你，就像一个朋友，每天晚上陪伴在你左右，一同分享甜美的梦亦或是一同经历可怕的梦。