贪心算法解决区间覆盖问题：从KOI路灯题看算法本质与C++实现 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]内都至少有一个点被某个路灯照亮。注意路灯的照亮范围是连续的且每个路灯的覆盖范围相同。关键点解析输入路灯的照射长度L区间数量N以及N个区间的左右端点L_i, R_i。输出一个整数即所需的最少路灯数量。目标最小化路灯数量覆盖所有需求区间。这立刻让我们联想到经典的“区间覆盖”问题。但和我们熟知的“用最少的点覆盖所有区间”每个点可以覆盖包含它的所有区间不同这里的“点”变成了一个长度为L的连续区间且这个区间路灯覆盖范围的起点是我们自由选择的。这增加了问题的复杂度。2.2 问题转化与贪心策略推导如何下手面对优化问题一个有效的思考方式是先考虑一个更弱的问题如果只要求覆盖所有区间不要求最少怎么放很容易想到在每个需求区间里随便放一个路灯就行了。但这显然不是最优的因为一个路灯可能同时覆盖多个需求区间。贪心算法的核心思想是每一步都做出当前看起来最优的选择并希望最终结果也是全局最优的。对于本题一个经典的贪心策略是排序将所有需要被照亮的区间按照右端点从小到大排序。如果右端点相同则按左端点排序有时左端点的顺序不影响核心逻辑但保持确定性是好习惯。遍历与放置依次处理每个区间。维护一个变量last_light表示最后一个放置的路灯所能覆盖到的最右位置。决策对于当前区间[l, r]如果last_light r说明这个区间已经被之前放置的路灯完全覆盖了因为上一个路灯的覆盖范围终点超过了当前区间的右端点直接跳过。否则说明当前区间未被完全覆盖。我们需要放置一个新的路灯。那么这个新路灯放在哪里最优贪心的策略是尽可能往右放让它能覆盖到当前区间同时为后续区间提供最大的覆盖潜力。这个最优位置就是max(l, last_light)。但要注意路灯覆盖范围是[pos, posL]。为了确保覆盖当前区间我们需要pos r且posL 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, posL]。我们希望pos尽可能小以覆盖更左的部分但同时要满足pos max(l, last_covered)且posL max(l, last_covered)这有点乱。让我们换一种更清晰、更不易出错的贪心思路也是竞赛中常见的标准解法将所有需求区间按左端点从小到大排序。初始化last_covered -INFans 0。遍历每个区间[l, r] a. 如果last_covered r说明该区间已被完全覆盖continue。 b. 如果last_covered l说明该区间与之前覆盖的区域无重叠我们必须至少用一个新灯来覆盖它。为了覆盖这个区间我们需要在区间内放置一个灯。为了让这个灯也能尽可能覆盖后面的区间我们将其放在pos l处吗不我们应该放在能覆盖当前区间且最靠右的位置即pos r。但考虑到灯的长度L如果放在r覆盖范围是[r, rL]这能覆盖[l, r]当且仅当r l且rL r显然成立但r可能小于l不对r是右端点肯定 l。但这样放置真的最优吗假设L5, 区间是[10, 12]。放在pos12覆盖[12,17]反而没覆盖到10和11这显然是错误的。所以放置点必须保证整个区间[l, r]都在路灯的覆盖范围[pos, posL]内。因此正确的贪心策略是将所有区间按左端点从小到大排序。设置current_pos -INF表示当前考虑到的、已被覆盖或即将被覆盖的连续区域的最右端。设置count 0。遍历每个区间[l, r]如果current_pos r跳过。否则如果current_pos l说明出现了“断层”我们需要在新区间上放置路灯。为了覆盖[l, r]我们至少需要将路灯的起始点pos设置在 l的位置并且posL r。为了让这个路灯也能覆盖尽可能多的后续区间我们选择pos l。放置后这个路灯覆盖了[l, lL]。那么更新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_posL]它肯定覆盖了[current_pos, r]如果current_posL r。但题目要求是覆盖整个[l, r]而[l, current_pos]这部分已经被之前的路灯覆盖了因为current_pos就是之前覆盖的最右端所以只要新灯覆盖了[current_pos, r]整个区间就被覆盖了。因此我们需要在放灯前确保current_pos L r不如果current_pos L r那么即使放了灯[current_posL, r]这段还是没被覆盖我们需要继续放灯。所以在l current_pos r的情况下我们可能需要放置多个路灯直到current_pos r。综上所述更普适的算法流程如下按左端点排序区间。covered_until -INFans 0。对于每个区间[l, r]如果covered_until r跳过。否则将l与covered_until比较取最大值作为需要开始覆盖的起点start max(l, covered_until)。计算从start开始要覆盖到r需要多少个长度为L的段。即need ceil((r - start) / L)。这里ceil是向上取整。放置need个路灯。这些路灯可以连续放置第一个放在start第二个放在startL以此类推。它们会覆盖到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 数据结构定义与输入处理首先我们需要存储区间。通常使用pairint, 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; vectorpairint, int intervals(N); for (int i 0; i N; i) { cin intervals[i].first intervals[i].second; } // 排序按左端点升序左端点相同时按右端点升序 sort(intervals.begin(), intervals.end()); // 核心算法实现 // ... return 0; }注意事项使用vectorpairint,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;关键点解析covered_until的初始化初始化为一个极小的负数如-1e18表示左边没有任何覆盖。不能初始化为0因为区间坐标可能为负。start的计算start max(l, covered_until)。如果covered_until l说明出现了断层从l开始覆盖如果covered_until在区间内部则从covered_until开始覆盖剩余部分。向上取整的技巧计算need ceil((r - start) / L)。在C中整数除法是向下取整。标准的向上取整写法是(a b - 1) / b。所以need (r - start L - 1) / L。这是非常容易出错的地方务必牢记。数据类型covered_until、start、need这些变量在计算过程中可能会很大例如start need * L所以使用long long是更安全的选择避免溢出。尽管输入是int但中间计算可能超出int范围。更新covered_untilcovered_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; // 读取所有区间 vectorpairint, 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; }手动模拟测试假设L5, 区间为[1,3], [4,6], [8,12]。排序后不变。初始化covered_until -INF,ans0。处理[1,3]:covered_until(-INF) 3继续。start max(1, -INF) 1。need (3-15-1)/5 (24)/5 6/5 1(整数除法)。covered_until 1 1*5 6。ans 1。处理[4,6]:covered_until(6) 6跳过。处理[8,12]:covered_until(6) 12继续。start max(8, 6) 8。need (12-85-1)/5 (44)/5 8/5 1(整数除法实际是1.6向上取整为2等等计算错了)。 正确计算(12-85-1) 8,8/5 1(整数除法向下取整为1)。但我们需要覆盖[8,12]长度是4一个长度5的路灯放在8可以覆盖[8,13]完全覆盖[8,12]所以need确实是1。我的向上取整公式(ab-1)/b在这里a4, b5,(45-1)/58/51正确。covered_until 8 1*5 13。ans 2。 输出2正确。第一个灯放在1覆盖[1,6]第二个灯放在8覆盖[8,13]。4. 边界条件与常见错误排查即使算法思路正确实现时也极易在边界条件上栽跟头。下面是我在调试这类问题时总结的几个“坑点”。4.1 数据类型溢出这是最隐蔽的错误之一。考虑以下情况L 1e9N 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-start10,L5公式(105-1)/5 14/5 2向下取整但我们实际需要10/52个灯。公式(ab-1)/b在a是b的倍数时(ab-1) a b -1除以b向下取整等于(a/b) (b-1)/b的整数部分由于(b-1)/b 1所以结果还是a/b。验证(105-1)14,14/52正确。当r-start不能被L整除时例如r-start11,L5(115-1)/515/53正确。极端情况r - start 0。在我们的逻辑中如果covered_until r会直接跳过所以进入计算need分支时一定有r start因此r - start 0。所以公式是安全的。4.4 浮点数陷阱有些初学者可能会想用ceil((double)(r-start)/L)。这虽然直观但引入了浮点数运算可能因精度问题导致错误例如当数字很大时。在竞赛编程中除非万不得已否则避免使用浮点数。整数运算的(ab-1)/b技巧是必须掌握的基本功。4.5 初始值设置covered_until的初始值必须小于任何可能的区间左端点。通常区间坐标在-1e9到1e9之间所以初始化为-1e18或LLONG_MIN需#include climits是安全的。如果初始化为0而第一个区间是[-10, -5]那么max(l, covered_until) max(-10, 0) 0计算出的start0但区间是[-10,-5]从0开始覆盖显然是错的。所以初始值必须足够小。5. 算法正确性证明与复杂度分析5.1 贪心选择性质证明为什么上述贪心策略每次在未覆盖区间的最左端需要开始覆盖的地方连续放置尽可能少的路灯以覆盖该区间是最优的我们可以用交换论证法来简要证明。假设存在一个最优解OPT我们将其与贪心解GREEDY进行比较。考虑第一个两者做出不同选择的位置。贪心解选择在位置start开始放置若干个路灯直到覆盖当前区间[l, r]。而OPT在这个位置可能选择了不同的放置点或数量。数量不可能更少贪心解放置的路灯数量need是覆盖从start到r所必需的最小数量因为我们是连续放置且每个灯发挥最大效用need ceil((r-start)/L)。任何其他方案要覆盖这段距离至少也需要need个路灯。所以OPT在此处使用的路灯数量不可能少于need。覆盖范围贪心解放置这need个路灯后覆盖的最右端是start need*L。这是在这need个路灯约束下能覆盖到的最右位置因为它们是连续紧挨着放的。OPT如果使用相同数量的路灯其覆盖的最右端不可能超过这个值假设路灯覆盖长度固定。如果OPT使用更多路灯显然不是更优。后续影响贪心解覆盖到了更右的位置或相同这为后续区间提供了更好的基础不会比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中都属于中等难度的基础题。它考察的不仅仅是贪心策略还有将实际问题抽象为数学模型的能力、对边界条件的处理、以及对整数运算和数据类型范围的敏感度。通过这道题我们可以巩固以下知识点自定义结构体/pair的排序。贪心算法的证明思路。向上取整的整数实现。循环遍历与状态更新。数据类型的选择与溢出预防。7. 调试技巧与实战心得在竞赛或练习中如何快速验证代码的正确性以下是我常用的方法小数据暴力对拍写一个朴素的暴力算法例如DFS枚举所有放灯位置用于小数据范围如N10坐标范围小的随机测试。生成随机数据分别运行贪心算法和暴力算法比较结果是否一致。这是发现逻辑错误最有效的方法。构造极端测试用例所有区间都重叠例如[1,100]重复N次。答案应为ceil(100/L)。区间互不重叠且间隔很大例如[1,2], [100,101], [200,201]。答案应为3 * ceil(1/L)通常每个区间需要一个灯。L1的情况此时每个单位长度都需要一个灯相当于求所有区间的并集长度。L非常大的情况例如L1e9区间都很小。可能一个灯就能覆盖所有区间。包含负数坐标的区间检查初始化是否正确。单步调试与打印中间变量在关键步骤如每次更新covered_until和ans后打印出它们的值与手动模拟的结果对比。静态检查代码所有变量是否使用了合适的数据类型long longvsint排序的关键字是否正确按左端点向上取整的公式是否正确(ab-1)/b初始值是否足够小covered_until循环中是否正确处理了跳过条件if (covered_until r)个人踩坑记录我曾经在一次练习中因为将covered_until初始化为0而测试数据第一个区间是负坐标导致WAWrong Answer。还有一次在计算need时我写了(r-start)/L ((r-start)%L ! 0)虽然逻辑正确但不如(r-startL-1)/L简洁而且在r-start为负数时理论上不会进入这个分支取模运算可能产生意外结果。所以统一使用(ab-1)/b这个公式并确保所有运算在long long中进行是更稳妥的做法。最后对于信奥选手来说刷题不仅要ACAccept更要理解每一道题背后的算法思想、编码细节和易错点。像P12648这样的题目吃透一道胜过模糊地刷十道。希望这篇详细的拆解能帮助你彻底掌握“路灯”类问题在未来的竞赛中遇到类似题目时能够迅速识别模型写出正确且高效的代码。