在你窗外闪耀的星星

GitHub 跳转原题关系图返回列表

先把同一坐标上的星星亮度合并，再把题目转成一维数组上固定长度窗口的最大区间和，用前缀和线性扫描即可。

OJ: luogu

题目 ID: P3353

难度:普及-

标签:前缀和滑动窗口数组模拟

日期: 2026-06-21 01:50

题意

数轴上有 $N$ 颗星星，第 $i$ 颗星星在位置 $X_i$ ，亮度为 $B_i$ 。

窗户一次能看到一个宽度为 $W$ 的范围，边界上的星星也算被看到。

题目要求我们移动窗户位置，使窗口内所有星星的亮度和最大，并输出这个最大值。

要注意两件事：

同一个位置上可能有多颗星星
当 $W=0$ 时，实际上只能看到某一个精确位置上的星星

思路

先看一个最直接、最容易理解的暴力写法：

cpp

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

int n, w;
int x[MAXN];
int b[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> w;
    int min_pos = 1000000000;
    int max_pos = 0;

    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> b[i];
        if (x[i] < min_pos) {
            min_pos = x[i];
        }
        if (x[i] > max_pos) {
            max_pos = x[i];
        }
    }

    int answer = 0;

    if (w == 0) {
        // 没有边缘时，只能选中一个精确位置。
        for (int pos = min_pos; pos <= max_pos; pos++) {
            int current = 0;
            for (int i = 1; i <= n; i++) {
                if (x[i] == pos) {
                    current += b[i];
                }
            }
            if (current > answer) {
                answer = current;
            }
        }
    } else {
        int half = w / 2;
        // 枚举窗户中心位置，直接判断每颗星星是否落在窗口内。
        for (int center = min_pos - half; center <= max_pos + half; center++) {
            int left = center - half;
            int right = center + half;
            int current = 0;
            for (int i = 1; i <= n; i++) {
                if (left <= x[i] && x[i] <= right) {
                    current += b[i];
                }
            }
            if (current > answer) {
                answer = current;
            }
        }
    }

    cout << answer << '\n';

    return 0;
}

brute.cpp 的思路很直白：

枚举窗户位置
对每个位置重新扫描所有星星
判断这颗星星是否落在窗口内

这个做法是对的，但会重复扫描很多次，复杂度太高，只适合做理解题意和小数据对拍。

真正的关键是先做一次坐标聚合。

如果同一个位置上有多颗星星，那么无论窗户怎么放，只要覆盖到这个位置，它们的贡献都会一起加进去。

所以可以先定义：

$a[x]$ 为位置 $x$ 上所有星星亮度之和

这样题目就从“很多星星”变成了“一个一维数组”：

若 $W=0$ ，答案就是 $a[x]$ 的最大值
若 $W>0$ ，答案就是连续 $W$ 个整数位置上的最大区间和

接下来做前缀和：

$prefix\_sum[i] = a[1] + a[2] + \dots + a[i]$

于是任意区间 $[l, r]$ 的亮度和都能在 $O(1)$ 算出来：

$prefix\_sum[r] - prefix\_sum[l - 1]$

最后枚举每个窗口的右端点 $right$ ：

左端点 $left = right - W + 1$
当前窗口和就是 $prefix\_sum[right] - prefix\_sum[left - 1]$

一路取最大值即可。

代码

cpp

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#include <bits/stdc++.h>
using namespace std;

const int MAXX = 100000 + 5;

int n, w;
int sum_brightness[MAXX];
int prefix_sum[MAXX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> w;
    int max_pos = 0;

    for (int i = 1; i <= n; i++) {
        int x, b;
        cin >> x >> b;
        sum_brightness[x] += b;
        if (x > max_pos) {
            max_pos = x;
        }
    }

    for (int i = 1; i <= max_pos; i++) {
        prefix_sum[i] = prefix_sum[i - 1] + sum_brightness[i];
    }

    int answer = 0;

    if (w == 0) {
        // W=0 时，窗户只能看到某一个精确位置上的星星。
        for (int i = 1; i <= max_pos; i++) {
            if (sum_brightness[i] > answer) {
                answer = sum_brightness[i];
            }
        }
    } else {
        // 题目保证 W 为奇数，此时长度为 W 的闭区间恰好覆盖连续 W 个整数位置。
        for (int right = 1; right <= max_pos; right++) {
            int left = right - w + 1;
            if (left < 1) {
                left = 1;
            }
            int current = prefix_sum[right] - prefix_sum[left - 1];
            if (current > answer) {
                answer = current;
            }
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

设最大坐标为 $M$ ，题目中 $M \leqslant 10^5$ 。

读入并聚合： $O(N)$
求前缀和： $O(M)$
枚举所有窗口： $O(M)$

总时间复杂度：

$O(N + M)$

空间复杂度：

$O(M)$

总结

这题的难点不在算法本身，而在建模转换：

原题说的是“星星散落在数轴上”
真正做时要先把它变成“每个位置有多少总亮度”

一旦完成这一步，题目就退化成了非常标准的定长最大区间和问题。

P3353 在你窗外闪耀的星星

题目背景

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

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

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

再见了，我的公主！

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

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

样例说明：

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

对于 $40\%$ 的数据， $W\leq 1000$ ；

对于 $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$ 的奇数。

在你窗外闪耀的星星

目录

题意

思路

代码

复杂度

总结