首页/资讯中心/详情

贪心算法解决区间覆盖问题：从KOI路灯题看算法本质与C++实现

贪心算法解决区间覆盖问题：从KOI路灯题看算法本质与C++实现
📅 发布时间：2026/7/14 4:55:56

1. 项目概述：从一道KOI竞赛题看路灯问题的算法本质

最近在带学生准备信息学奥赛（信奥）和KOI（克罗地亚信息学奥林匹克）的刷题训练时，遇到了P12648这道关于“路灯”的题目。题目本身描述了一个看似简单的场景：在一条笔直的道路上安装路灯，但约束条件却非常典型，涉及区间覆盖、资源优化和边界处理，是竞赛中常见的“贪心”或“动态规划”类问题的绝佳载体。很多初学者看到“路灯”二字，可能下意识地想到模拟开关灯，但这道题的核心其实是如何在满足照亮所有指定区间的前提下，最优化地放置路灯，考验的是将实际问题抽象为数学模型并设计高效算法的能力。

这道题源自KOI 2024第二轮，其质量相当高，不仅考察选手对C++基础数据结构和循环的控制能力，更深入到了贪心策略的证明与边界条件的细致处理。对于正在备战CSP-J/S、NOIP甚至更高阶竞赛的选手来说，这类题目是锻炼逻辑思维和代码实现严谨性的宝贵材料。本文将带你彻底拆解P12648，从理解题意、抽象模型、设计算法，到用C++实现并处理所有魔鬼细节，最后分享我在调试这类问题时的实战心得。无论你是刚接触信奥的新手，还是想巩固贪心算法细节的进阶者，相信这篇详尽的拆解都能让你有所收获。

2. 问题解析与数学模型建立

2.1 题目重述与核心需求

我们先抛开原题的英文或克罗地亚语描述，用中文梳理一下核心需求。题目通常是这样描述的：

有一条无限长的数轴（代表道路）。现在有N个区间，第i个区间是[L_i, R_i]，表示这段路需要被照亮。你拥有一种路灯，每个路灯如果安装在位置x，可以照亮区间[x, x + L]（其中L是路灯的照射长度，一个固定值）。我们的目标是，安装尽可能少的路灯，使得每一个给定的需求区间[L_i, R_i]内都至少有一个点被某个路灯照亮。注意，路灯的照亮范围是连续的，且每个路灯的覆盖范围相同。

关键点解析：

  1. 输入：路灯的照射长度L，区间数量N，以及N个区间的左右端点L_i, R_i。
  2. 输出：一个整数，即所需的最少路灯数量。
  3. 目标：最小化路灯数量，覆盖所有需求区间。

这立刻让我们联想到经典的“区间覆盖”问题。但和我们熟知的“用最少的点覆盖所有区间”（每个点可以覆盖包含它的所有区间）不同，这里的“点”变成了一个长度为L的连续区间，且这个区间（路灯覆盖范围）的起点是我们自由选择的。这增加了问题的复杂度。

2.2 问题转化与贪心策略推导

如何下手？面对优化问题，一个有效的思考方式是先考虑一个更弱的问题：如果只要求覆盖所有区间，不要求最少，怎么放？很容易想到，在每个需求区间里随便放一个路灯就行了。但这显然不是最优的，因为一个路灯可能同时覆盖多个需求区间。

贪心算法的核心思想是每一步都做出当前看起来最优的选择，并希望最终结果也是全局最优的。对于本题，一个经典的贪心策略是：

  1. 排序：将所有需要被照亮的区间按照右端点从小到大排序。如果右端点相同，则按左端点排序（有时左端点的顺序不影响核心逻辑，但保持确定性是好习惯）。
  2. 遍历与放置：依次处理每个区间。维护一个变量last_light，表示最后一个放置的路灯所能覆盖到的最右位置。
  3. 决策：对于当前区间[l, r]：
    • 如果last_light >= r，说明这个区间已经被之前放置的路灯完全覆盖了（因为上一个路灯的覆盖范围终点超过了当前区间的右端点），直接跳过。
    • 否则，说明当前区间未被完全覆盖。我们需要放置一个新的路灯。那么，这个新路灯放在哪里最优？贪心的策略是：尽可能往右放，让它能覆盖到当前区间，同时为后续区间提供最大的覆盖潜力。这个最优位置就是max(l, last_light)。但要注意，路灯覆盖范围是[pos, pos+L]。为了确保覆盖当前区间，我们需要pos <= r且pos+L >= l？不，更精确的思考是：我们希望这个新路灯的覆盖范围能覆盖当前区间尚未被覆盖的部分，尤其是右半部分。 实际上，更直观的做法是：当发现当前区间[l, r]的l > last_light时（即左端点都未被覆盖），我们必须在当前区间内放置一个灯。为了让这个灯发挥最大效用，我们应该把它放在能覆盖当前区间且尽可能靠右的位置，即pos = r。但放在r可能不是最优，因为如果L很大，放在r会导致覆盖范围大量向右溢出，对左侧未覆盖部分帮助不大。正确的贪心放置点是pos = max(l, last_light)吗？让我们仔细分析。

贪心策略的严谨推导：我们重新定义状态。设last_covered为当前已被路灯覆盖到的最右坐标（注意，不是路灯位置，是已覆盖区域的最右端）。 对于当前区间[l, r]：

  • 如果last_covered >= r，区间已被完全覆盖，跳过。
  • 如果last_covered < r，则需要新的路灯。新路灯应放在何处？我们要让它覆盖从last_covered之后（即last_covered这个点本身可能已被覆盖，但我们需要覆盖last_covered右侧的点）到当前区间r的部分。为了最大化利用，新路灯的覆盖起点应尽可能靠左，但必须保证能覆盖到last_covered之后的部分。实际上，最贪心的放置方式是：让新路灯的覆盖区间的左端点刚好等于max(l, last_covered)。但路灯是一个固定长度为L的区间[pos, pos+L]。我们希望pos尽可能小，以覆盖更左的部分，但同时要满足pos <= max(l, last_covered)且pos+L >= max(l, last_covered)？这有点乱。

让我们换一种更清晰、更不易出错的贪心思路，也是竞赛中常见的标准解法：

  1. 将所有需求区间按左端点从小到大排序。
  2. 初始化last_covered = -INF，ans = 0。
  3. 遍历每个区间[l, r]： a. 如果last_covered >= r，说明该区间已被完全覆盖，continue。 b. 如果last_covered < l，说明该区间与之前覆盖的区域无重叠，我们必须至少用一个新灯来覆盖它。为了覆盖这个区间，我们需要在区间内放置一个灯。为了让这个灯也能尽可能覆盖后面的区间，我们将其放在pos = l处吗？不，我们应该放在能覆盖当前区间且最靠右的位置，即pos = r。但考虑到灯的长度L，如果放在r，覆盖范围是[r, r+L]，这能覆盖[l, r]当且仅当r >= l且r+L >= r显然成立，但r可能小于l？不对，r是右端点，肯定>= l。但这样放置真的最优吗？假设L=5, 区间是[10, 12]。放在pos=12，覆盖[12,17]，反而没覆盖到10和11！这显然是错误的。所以，放置点必须保证整个区间[l, r]都在路灯的覆盖范围[pos, pos+L]内。

因此，正确的贪心策略是：

  1. 将所有区间按左端点从小到大排序。
  2. 设置current_pos = -INF，表示当前考虑到的、已被覆盖或即将被覆盖的连续区域的最右端。
  3. 设置count = 0。
  4. 遍历每个区间[l, r]：
    • 如果current_pos >= r，跳过。
    • 否则，如果current_pos < l，说明出现了“断层”，我们需要在新区间上放置路灯。为了覆盖[l, r]，我们至少需要将路灯的起始点pos设置在<= l的位置，并且pos+L >= r。为了让这个路灯也能覆盖尽可能多的后续区间，我们选择pos = l。放置后，这个路灯覆盖了[l, l+L]。那么更新current_pos = l + L。count++。
    • 否则，如果l <= current_pos < r，说明当前区间有一部分已被覆盖，但右半部分[current_pos, r]还未被覆盖。我们仍然需要放置一个新路灯来覆盖剩余部分。此时，为了让新路灯同时覆盖未覆盖部分并尽可能延伸，我们将新路灯放在pos = current_pos。放置后，覆盖[current_pos, current_pos + L]。更新current_pos = current_pos + L。count++。

但这个策略在l <= current_pos < r时，将灯放在current_pos，能保证覆盖[l, r]吗？新覆盖范围是[current_pos, current_pos+L]，它肯定覆盖了[current_pos, r]如果current_pos+L >= r。但题目要求是覆盖整个[l, r]，而[l, current_pos]这部分已经被之前的路灯覆盖了（因为current_pos就是之前覆盖的最右端），所以只要新灯覆盖了[current_pos, r]，整个区间就被覆盖了。因此，我们需要在放灯前确保current_pos + L >= r？不，如果current_pos + L < r，那么即使放了灯，[current_pos+L, r]这段还是没被覆盖，我们需要继续放灯。所以，在l <= current_pos < r的情况下，我们可能需要放置多个路灯，直到current_pos >= r。

综上所述，更普适的算法流程如下：

  1. 按左端点排序区间。
  2. covered_until = -INF，ans = 0。
  3. 对于每个区间[l, r]：
    • 如果covered_until >= r，跳过。
    • 否则，将l与covered_until比较，取最大值作为需要开始覆盖的起点start = max(l, covered_until)。
    • 计算从start开始，要覆盖到r，需要多少个长度为L的段。即need = ceil((r - start) / L)。这里ceil是向上取整。
    • 放置need个路灯。这些路灯可以连续放置，第一个放在start，第二个放在start+L，以此类推。它们会覆盖到start + need * L。
    • 更新covered_until = start + need * L。
    • ans += need。

这个算法才是清晰且正确的。它等价于：在数轴上，从最左端开始，每次遇到未被覆盖的区间，就在该区间内尽可能靠左地放置路灯（但紧挨着已覆盖区域），直到这个区间被完全覆盖，然后更新已覆盖的最右坐标。

2.3 数据范围与算法选择

KOI竞赛的题目通常会给出数据范围，这直接决定了我们算法的可行性。假设题目中N最大为10^5，坐标范围在[-10^9, 10^9]之间。那么：

  • O(N^2)的暴力枚举肯定超时。
  • O(N log N)的排序加贪心是可行的。 我们上面推导的贪心算法，排序复杂度O(N log N)，遍历处理每个区间复杂度O(N)，总体O(N log N)，完全可以应对。

这里选择贪心而非动态规划，是因为问题具有“贪心选择性质”和“最优子结构”。简单来说，在当前已覆盖区域的基础上，总是选择在未覆盖区间的最左端尽可能放置路灯（以覆盖该区间并尽可能向右延伸），这个局部最优选择能导致全局最优解。这可以通过反证法来证明：如果存在一个最优解，其第一个与贪心解不同的选择，我们可以将其替换为贪心选择而不使解变差，从而证明贪心解至少和最优解一样好。

3. C++实现详解与代码逐行解析

理解了算法，接下来就是用C++将其实现。这里不仅会给出代码，还会逐行解释关键点，并讨论一些常见的实现陷阱。

3.1 数据结构定义与输入处理

首先，我们需要存储区间。通常使用pair<int, int>或者自定义结构体。由于坐标范围可能很大（10^9），但数量不多，用int通常足够（32位有符号整数范围约±21亿）。但为了安全，有时题目会要求用long long。这里我们先按int处理。

#include <iostream> #include <vector> #include <algorithm> #include <cmath> // 用于ceil函数 using namespace std; int main() { int L, N; cin >> L >> N; vector<pair<int, int>> intervals(N); for (int i = 0; i < N; ++i) { cin >> intervals[i].first >> intervals[i].second; } // 排序：按左端点升序，左端点相同时按右端点升序 sort(intervals.begin(), intervals.end()); // 核心算法实现 // ... return 0; }

注意事项：

  • 使用vector<pair<int,int>>存储区间，first是左端点，second是右端点。
  • sort默认对pair按first升序排序，first相等时按second升序，这符合我们的需求。
  • 输入处理是竞赛编程的基础，务必保证快速准确。这里假设输入格式是先L和N，然后是N行区间。

3.2 贪心算法核心逻辑实现

接下来实现算法的核心部分。我们需要跟踪covered_until（当前已覆盖到的最右坐标），并遍历排序后的区间。

long long covered_until = -1e18; // 初始化为一个非常小的数，表示尚未覆盖任何区域 int ans = 0; for (const auto& interval : intervals) { int l = interval.first; int r = interval.second; // 如果当前区间已经被完全覆盖，则跳过 if (covered_until >= r) { continue; } // 计算需要开始覆盖的起点 long long start = max((long long)l, covered_until); // 计算需要多少个路灯才能覆盖从start到r // 注意：这里要避免整数除法的问题 long long need = (r - start + L - 1) / L; // 向上取整的技巧 // 更新已覆盖的最右端 covered_until = start + need * L; // 累加路灯数量 ans += need; } cout << ans << endl;

关键点解析：

  1. covered_until的初始化：初始化为一个极小的负数（如-1e18），表示左边没有任何覆盖。不能初始化为0，因为区间坐标可能为负。
  2. start的计算：start = max(l, covered_until)。如果covered_until < l，说明出现了断层，从l开始覆盖；如果covered_until在区间内部，则从covered_until开始覆盖剩余部分。
  3. 向上取整的技巧：计算need = ceil((r - start) / L)。在C++中，整数除法是向下取整。标准的向上取整写法是(a + b - 1) / b。所以need = (r - start + L - 1) / L。这是非常容易出错的地方，务必牢记。
  4. 数据类型：covered_until、start、need这些变量在计算过程中可能会很大（例如start + need * L），所以使用long long是更安全的选择，避免溢出。尽管输入是int，但中间计算可能超出int范围。
  5. 更新covered_until：covered_until = start + need * L。注意，这里计算出的covered_until可能远远超过当前区间的r，这是正确的，因为它代表了放置这need个路灯后实际覆盖到的最右端，可能已经覆盖了后面的区间。

3.3 完整代码与测试用例

将以上部分组合起来，并添加一些注释，得到完整代码：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // 输入路灯照射长度和区间数量 int L, N; cin >> L >> N; // 读取所有区间 vector<pair<int, int>> intervals(N); for (int i = 0; i < N; ++i) { cin >> intervals[i].first >> intervals[i].second; } // 按左端点升序排序 sort(intervals.begin(), intervals.end()); long long covered_until = -1e18; // 当前已覆盖的最右位置，初始化为负无穷 int ans = 0; // 路灯总数 for (const auto& interval : intervals) { int l = interval.first; int r = interval.second; // 如果当前区间已被完全覆盖，跳过 if (covered_until >= r) { continue; } // 计算需要开始覆盖的起点 long long start = max((long long)l, covered_until); // 计算需要多少个路灯 (向上取整) // 注意：这里(r - start)可能为0，但need至少为1？不，如果start >= r，前面已经跳过了。 // 所以这里 (r - start) > 0 long long need = (r - start + L - 1) / L; // 更新已覆盖的最右端 covered_until = start + need * L; // 累加答案 ans += need; } cout << ans << endl; return 0; }

手动模拟测试：假设L=5, 区间为[1,3], [4,6], [8,12]。

  1. 排序后不变。
  2. 初始化covered_until = -INF,ans=0。
  3. 处理[1,3]:
    • covered_until(-INF) < 3，继续。
    • start = max(1, -INF) = 1。
    • need = (3-1+5-1)/5 = (2+4)/5 = 6/5 = 1(整数除法)。
    • covered_until = 1 + 1*5 = 6。
    • ans = 1。
  4. 处理[4,6]:
    • covered_until(6) >= 6，跳过。
  5. 处理[8,12]:
    • covered_until(6) < 12，继续。
    • start = max(8, 6) = 8。
    • need = (12-8+5-1)/5 = (4+4)/5 = 8/5 = 1(整数除法，实际是1.6，向上取整为2？等等，计算错了)。 正确计算：(12-8+5-1) = 8,8/5 = 1(整数除法向下取整为1)。但我们需要覆盖[8,12]，长度是4，一个长度5的路灯放在8可以覆盖[8,13]，完全覆盖[8,12]，所以need确实是1。我的向上取整公式(a+b-1)/b在这里：a=4, b=5,(4+5-1)/5=8/5=1，正确。
    • covered_until = 8 + 1*5 = 13。
    • ans = 2。 输出2，正确。第一个灯放在1，覆盖[1,6]；第二个灯放在8，覆盖[8,13]。

4. 边界条件与常见错误排查

即使算法思路正确，实现时也极易在边界条件上栽跟头。下面是我在调试这类问题时总结的几个“坑点”。

4.1 数据类型溢出

这是最隐蔽的错误之一。考虑以下情况：

  • L = 1e9
  • N = 1e5
  • 区间范围也是±1e9在计算start + need * L时，need可能达到N量级（最坏情况），need * L可能高达1e5 * 1e9 = 1e14，这远远超出了int（约2e9）的范围。即使start是long long，但need和L都是int，表达式need * L会先以int类型计算，导致溢出，然后才赋值给long long的covered_until，结果为错误值。

解决方案：在计算中，确保至少有一个操作数是long long类型。

// 正确做法 long long need = (r - start + L - 1) / L; // L被提升为long long covered_until = start + need * (long long)L; // 显式转换 // 或者更简洁地，将L定义为long long long long L; cin >> L;

在竞赛中，我习惯将可能涉及大数计算的变量统统定义为long long，省去转换的麻烦。

4.2 排序顺序与区间包含关系

我们的算法基于一个假设：区间按左端点排序后，处理顺序不会影响贪心策略的正确性。但这里有一个细微之处：如果存在区间包含关系呢？例如区间A[1,10]和区间B[3,5]。按左端点排序后是A、B。处理A时，我们可能放置路灯覆盖到很远（比如15），然后处理B时，发现covered_until(15) >= 5，直接跳过。这没问题。

但如果区间是[3,5]和[1,10]呢？排序后依然是[1,10],[3,5]。所以按左端点排序是安全的，它保证了我们先处理更靠左的区间，扩展覆盖范围，后续被包含的区间自然会被检查到。

但是，如果题目中的区间不是必须完全覆盖，而是只需要覆盖至少一个点，或者路灯的覆盖是点覆盖而非区间覆盖，那么排序策略可能需要调整（例如按右端点排序）。本题是区间完全覆盖，所以左端点排序是合适的。

4.3 向上取整的细节

计算need = ceil((r - start) / L)时，使用(r - start + L - 1) / L这个公式。但要注意：

  • 当r - start正好是L的倍数时，例如r-start=10,L=5，公式(10+5-1)/5 = 14/5 = 2（向下取整），但我们实际需要10/5=2个灯。公式(a+b-1)/b在a是b的倍数时，(a+b-1) = a + b -1，除以b向下取整等于(a/b) + (b-1)/b的整数部分，由于(b-1)/b < 1，所以结果还是a/b。验证：(10+5-1)=14,14/5=2，正确。
  • 当r-start不能被L整除时，例如r-start=11,L=5，(11+5-1)/5=15/5=3，正确。
  • 极端情况：r - start <= 0。在我们的逻辑中，如果covered_until >= r会直接跳过，所以进入计算need分支时，一定有r > start，因此r - start > 0。所以公式是安全的。

4.4 浮点数陷阱

有些初学者可能会想用ceil((double)(r-start)/L)。这虽然直观，但引入了浮点数运算，可能因精度问题导致错误（例如当数字很大时）。在竞赛编程中，除非万不得已，否则避免使用浮点数。整数运算的(a+b-1)/b技巧是必须掌握的基本功。

4.5 初始值设置

covered_until的初始值必须小于任何可能的区间左端点。通常区间坐标在-1e9到1e9之间，所以初始化为-1e18或LLONG_MIN（需#include <climits>）是安全的。如果初始化为0，而第一个区间是[-10, -5]，那么max(l, covered_until) = max(-10, 0) = 0，计算出的start=0，但区间是[-10,-5]，从0开始覆盖显然是错的。所以初始值必须足够小。

5. 算法正确性证明与复杂度分析

5.1 贪心选择性质证明

为什么上述贪心策略（每次在未覆盖区间的最左端需要开始覆盖的地方，连续放置尽可能少的路灯以覆盖该区间）是最优的？

我们可以用交换论证法来简要证明。假设存在一个最优解OPT，我们将其与贪心解GREEDY进行比较。考虑第一个两者做出不同选择的位置。贪心解选择在位置start开始放置若干个路灯，直到覆盖当前区间[l, r]。而OPT在这个位置可能选择了不同的放置点或数量。

  1. 数量不可能更少：贪心解放置的路灯数量need是覆盖从start到r所必需的最小数量（因为我们是连续放置，且每个灯发挥最大效用，need = ceil((r-start)/L)）。任何其他方案要覆盖这段距离，至少也需要need个路灯。所以OPT在此处使用的路灯数量不可能少于need。
  2. 覆盖范围：贪心解放置这need个路灯后，覆盖的最右端是start + need*L。这是在这need个路灯约束下能覆盖到的最右位置（因为它们是连续紧挨着放的）。OPT如果使用相同数量的路灯，其覆盖的最右端不可能超过这个值（假设路灯覆盖长度固定）。如果OPT使用更多路灯，显然不是更优。
  3. 后续影响：贪心解覆盖到了更右的位置（或相同），这为后续区间提供了更好的基础，不会比OPT差。

因此，贪心解在每一步都不比最优解差，最终结果也是最优的。

5.2 时间复杂度与空间复杂度分析

  • 时间复杂度：
    • 排序：O(N log N)，其中N是区间数量。
    • 线性扫描：O(N)。
    • 总复杂度：O(N log N)，对于N <= 10^5绰绰有余。
  • 空间复杂度：
    • 存储区间需要O(N)空间。
    • 其他变量常数空间。
    • 总空间复杂度O(N)。

这是此类问题的最优复杂度，因为至少需要读取和存储所有输入。

6. 变种与扩展思考

掌握了基础模型后，我们可以思考一些变种问题，这有助于深化理解。

6.1 变种一：路灯有不同长度

如果每种路灯的照射长度不同，或者有K种不同长度的路灯可供选择，目标仍然是覆盖所有区间且总成本最低（每个路灯成本可能不同）。这就变成了一个更复杂的动态规划或贪心+优先队列问题。可能需要按右端点排序，并使用DP状态dp[i]表示覆盖前i个区间的最小花费，转移时考虑在某个点放置哪种路灯。

6.2 变种二：区间是点集

如果需求不是连续区间，而是离散的点集（即需要照亮某些特定点），问题就退化为经典的“最小区间覆盖点”问题。可以使用类似的贪心：将点排序，每次放置一个路灯覆盖当前最左的未覆盖点，并尽可能向右覆盖更多的点，然后重复。

6.3 变种三：二维平面覆盖

如果道路不是直线，而是在二维平面上，路灯的覆盖范围是一个圆或正方形，需要覆盖二维平面上的多个矩形区域。这通常需要更复杂的几何算法，可能用到扫描线或近似算法。

6.4 在信奥/算法竞赛中的位置

P12648这类题属于“贪心算法”中的“区间覆盖”经典题。它在信奥赛、NOIP/省选乃至ACM/ICPC中都属于中等难度的基础题。它考察的不仅仅是贪心策略，还有将实际问题抽象为数学模型的能力、对边界条件的处理、以及对整数运算和数据类型范围的敏感度。通过这道题，我们可以巩固以下知识点：

  1. 自定义结构体/pair的排序。
  2. 贪心算法的证明思路。
  3. 向上取整的整数实现。
  4. 循环遍历与状态更新。
  5. 数据类型的选择与溢出预防。

7. 调试技巧与实战心得

在竞赛或练习中，如何快速验证代码的正确性？以下是我常用的方法：

  1. 小数据暴力对拍：写一个朴素的暴力算法（例如DFS枚举所有放灯位置），用于小数据范围（如N<=10，坐标范围小）的随机测试。生成随机数据，分别运行贪心算法和暴力算法，比较结果是否一致。这是发现逻辑错误最有效的方法。
  2. 构造极端测试用例：
    • 所有区间都重叠：例如[1,100]重复N次。答案应为ceil(100/L)。
    • 区间互不重叠且间隔很大：例如[1,2], [100,101], [200,201]。答案应为3 * ceil(1/L)，通常每个区间需要一个灯。
    • L=1的情况：此时每个单位长度都需要一个灯，相当于求所有区间的并集长度。
    • L非常大的情况：例如L=1e9，区间都很小。可能一个灯就能覆盖所有区间。
    • 包含负数坐标的区间：检查初始化是否正确。
  3. 单步调试与打印中间变量：在关键步骤（如每次更新covered_until和ans后）打印出它们的值，与手动模拟的结果对比。
  4. 静态检查代码：
    • 所有变量是否使用了合适的数据类型？（long longvsint）
    • 排序的关键字是否正确？（按左端点）
    • 向上取整的公式是否正确？(a+b-1)/b
    • 初始值是否足够小？（covered_until）
    • 循环中是否正确处理了跳过条件？（if (covered_until >= r)）

个人踩坑记录：我曾经在一次练习中，因为将covered_until初始化为0，而测试数据第一个区间是负坐标，导致WA（Wrong Answer）。还有一次，在计算need时，我写了(r-start)/L + ((r-start)%L != 0)，虽然逻辑正确，但不如(r-start+L-1)/L简洁，而且在r-start为负数时（理论上不会进入这个分支），取模运算可能产生意外结果。所以，统一使用(a+b-1)/b这个公式，并确保所有运算在long long中进行，是更稳妥的做法。

最后，对于信奥选手来说，刷题不仅要AC（Accept），更要理解每一道题背后的算法思想、编码细节和易错点。像P12648这样的题目，吃透一道，胜过模糊地刷十道。希望这篇详细的拆解能帮助你彻底掌握“路灯”类问题，在未来的竞赛中遇到类似题目时，能够迅速识别模型，写出正确且高效的代码。