【GESP】C++五级练习题 luogu-P3353 在你窗外闪耀的星星

GESP C++ 五级练习题，贪心思想和前缀和思想考点。题目难度⭐⭐★☆☆，适合五级入门和四级练习，洛谷难度等级普及-。

luogu-P3353 在你窗外闪耀的星星

题目要求

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

6 3
1 2
2 4
3 8
4 4
5 2
1000 1

输出 #1

16

说明/提示

样例说明：

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

---

题目分析

这道题目的核心是滑动窗口或前缀和的应用。题目要求我们在一个数轴上移动一个宽度为 $W$ 的“窗户”，使得窗户内包含的星星亮度之和最大。

1. 问题建模

• 数轴上有 $N$ 颗星星，每颗星星有位置 $X_i$ 和亮度 $B_i$。
• 注意：同一个位置可能有多颗星星。
• 窗户的宽度为 $W$。窗户覆盖的区间可以看作是 $[k, k+W-1]$（包含边界），长度为 $W$。我们需要找到一个起始位置 $k$，使得这个区间内的 $B_i$ 之和最大。

2. 解题思路

由于题目中给出的坐标范围 $X_i$ 较小（最大 $10^5$），我们可以考虑两种主要的方法：滑动窗口（双指针）和前缀和。

思路一：滑动窗口（双指针）

这种方法适用于坐标范围很大但星星数量 $N$ 相对较少的情况，或者直接基于排序后的星星进行处理。

1. 排序：首先将所有星星按照坐标 $X_i$ 从小到大排序。
2. 双指针扫描：使用两个指针 left 和 right（或者 start_idx 和 i）维护一个窗口。
3. 移动策略：
   • 不断移动右指针 right，将新的星星加入窗口，并累加亮度。
   • 检查当前窗口的覆盖范围（即 stars[right].x - stars[left].x + 1）是否超过了 $W$。
   • 如果超过了 $W$，则需要移动左指针 left，将窗口左侧的星星移出，并减去其亮度，直到窗口范围满足条件。
   • 在每次移动过程中，记录窗口内亮度的最大值。

思路二：前缀和（桶排序思想） – 推荐解法

由于坐标 $X_i$ 的最大值只有 $100000$，我们可以利用桶（Bucket）的思想，直接用数组下标代表坐标。

1. 数据映射：建立一个数组 a，a[x] 表示坐标 $x$ 处所有星星的亮度之和。注意处理同一位置多颗星星的情况，需要累加。
2. 前缀和计算：构建前缀和数组 pre，其中 pre[i] 表示从坐标 1 到 $i$ 的所有星星亮度之和。
   • 公式：pre[i] = pre[i-1] + a[i]
3. 区间查询：对于任意一个起点 $i$，宽度为 $W$ 的窗户覆盖的区间是 $[i, i+W-1]$。该区间内的亮度和可以通过前缀和 $O(1)$ 得到：Sum = pre[i+W-1] - pre[i-1]。
4. 枚举最大值：枚举所有可能的起点 $i$，计算对应的亮度和，取最大值即可。

这种方法代码编写简单，逻辑清晰，且时间复杂度为 $O(\max(X_i))$，在本题数据范围内非常高效。

---

示例代码

方法一、滑动窗口

#include <algorithm>
#include <iostream>

// 定义长整型别名，防止亮度累加溢出
typedef long long ll;

// 定义星星结构体，存储位置和亮度
struct Star {
    int x;      // 星星在数轴上的坐标
    int light;  // 星星的亮度
};

// 比较函数，用于按坐标 x 对星星进行升序排序
bool cmp(Star a, Star b) { return a.x < b.x; }

struct Star stars[100005];  // 存储所有星星的数组
int main() {
    int N, W;
    std::cin >> N >> W;
    for (int i = 0; i < N; i++) {
        std::cin >> stars[i].x >> stars[i].light;
    }
    // 将星星按位置坐标排序，方便使用滑动窗口
    std::sort(stars, stars + N, cmp);

    int start_idx = 0;  // 滑动窗口的左边界索引
    ll max_light = 0;   // 记录最大的亮度和
    ll cur_light = 0;   // 当前窗口内的亮度及

    // 双指针/滑动窗口主循环
    // i 代表窗口试图延伸到的右边界星星索引
    // start_idx 代表窗口当前的左边界星星索引
    for (int i = 0; i < N && start_idx < N;) {
        // 判断当前的星星 stars[i] 是否在以 stars[start_idx] 为起点的窗户范围内
        // 窗户宽度为 W，覆盖范围条件为：两星坐标差 + 1 <= W （即距离 <= W-1）
        // 这里的逻辑与样例输出即题目隐含的“窗户容量”相符
        if (stars[i].x - stars[start_idx].x + 1 <= W) {
            cur_light += stars[i].light;  // 如果在范围内，加上该星星亮度
            i++;                          // 右边界向右扩展
        } else {
            // 如果不在范围内，说明窗口需要向右移动，移除左边界星星
            cur_light -= stars[start_idx].light;
            start_idx++;  // 左边界向右收缩
        }
        // 每次变动后更新最大亮度记录
        max_light = std::max(max_light, cur_light);
    }
    std::cout << max_light << std::endl;
    return 0;
}

方法二、前缀和（推荐）

#include <algorithm>
#include <iostream>

// a[i] 表示坐标 i 处的星星总亮度
// 题目中坐标最大 X_i <= 100000，所以数组开到 100005 即可
int a[100005];
// pre[i] 表示前缀和数组，存储从坐标 1 到 i 的星星亮度总和
int pre[100005];

int main() {
    int N, W;
    std::cin >> N >> W;  // 输入星星数量 N 和窗户宽度 W

    for (int i = 1; i <= N; i++) {
        int x, b;
        std::cin >> x >> b;  // 输入每颗星星的坐标 x 和亮度 b
        // 注意：同一个位置可能有多颗星星，所以这里使用 += 累加亮度
        a[x] += b;
    }

    // 计算前缀和
    // pre[i] = a[1] + ... + a[i]
    for (int i = 1; i <= 100000; i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    int max_b = 0;  // 记录能看到的最大亮度

    // 枚举每一个可能的窗户起点 i
    // 窗户范围是 [i, i + W - 1]
    // 确保窗户右端点 i + W - 1 不超过最大坐标范围 100000
    for (int i = 1; i + W - 1 <= 100000; i++) {
        // 利用前缀和快速计算当前窗户内的亮度总和
        // 区间 [L, R] 的和为 pre[R] - pre[L-1]
        // 这里 L = i, R = i + W - 1
        int cur_b = pre[i + W - 1] - pre[i - 1];
        max_b = std::max(max_b, cur_b);  // 更新最大值
    }

    std::cout << max_b << std::endl;  // 输出结果
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号