csp信奥赛C++高频考点专项训练之贪心算法 --【区间贪心】：区间覆盖（加强版）

张

张建站

2026/4/25 5:19:30

10分钟阅读

csp信奥赛C高频考点专项训练之贪心算法 --【区间贪心】区间覆盖加强版题目描述已知有N NN个区间每个区间的范围是[ s i , t i ] [s_i,t_i][si,ti]请求出区间覆盖后的总长。输入格式第一行一个正整数N NN表示区间个数。接下来N NN行每行两个正整数表示s i s_isi和t i t_iti。输出格式共一行一个正整数为覆盖后的区间总长。输入输出样例 1输入 13 1 100000 200001 1000000 100000000 100000001输出 1900002说明/提示对于40 % 40 \%40%的数据N ≤ 1000 N \le 1000N≤10001 ≤ s i t i ≤ 10000 1 \le s_i t_i \le 100001≤siti≤10000。对于100 % 100 \%100%的数据 N ≤ 10 5 N \le 10^5N≤1051 ≤ s i t i ≤ 10 17 1 \le s_i t_i \le 10^{17}1≤siti≤1017。思路分析给定 N 个闭区间[ s i , t i ] [s_i, t_i][si,ti]需要求它们合并后的总长度。由于坐标最大可达10 17 10^{17}1017不能使用数组差分必须通过排序贪心合并。排序将所有区间按左端点升序排列。这样能保证从左到右依次处理当前区间只可能和后续区间重叠或相邻。合并初始化当前合并段的左右端点为第一个区间的l和r。遍历后续区间若当前区间的左端点a[i].l大于当前合并段的右端点cur说明两段之间有空隙无法合并。此时将当前段的长度cur - cul 1累加到答案并开始一个新的合并段用当前区间重置cul和cur。否则a[i].l cur说明有重叠或相邻闭区间下[1,2]和[3,4]不相邻因为3 2所以用判断不会错误合并不相邻区间此时更新当前段的右端点cur max(cur, a[i].r)。循环结束后将最后一段的长度加入答案。输出输出累加的总长度。时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)空间复杂度 O(N)。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;// 使用ll表示long long适应1e17的大数constintN1e510;// 最大区间数10intn;// 区间个数structnode{// 区间结构体ll l,r;// 左端点、右端点}a[N];// 存储所有区间boolcmp(node a,node b){// 按左端点升序排序的比较函数returna.lb.l;}intmain(){cinn;for(inti1;in;i){cina[i].la[i].r;}sort(a1,an1,cmp);// 将区间按左端点排序ll cula[1].l;// 当前合并段的左端点current leftll cura[1].r;// 当前合并段的右端点current rightll ans0;// 总覆盖长度for(inti2;in;i){// 从第二个区间开始合并if(a[i].lcur){// 当前区间与之前段不相连有间隙ans(cur-cul1);// 加上之前段的长度cula[i].l;// 开启新段左端点为当前区间左端点cura[i].r;// 右端点为当前区间右端点}else{// 可以合并curmax(cur,a[i].r);// 扩展当前段的右端点}}ans(cur-cul1);// 加上最后一段的长度coutans;// 输出结果return0;}功能分析输入处理读取整数 N 和 N 行区间每个区间包含左右端点。排序调用sort并传入自定义比较函数cmp将所有区间按照左端点从小到大排列。贪心合并维护当前合并段的左右端点cul和cur初始化为第一个区间。依次考察每个后续区间如果当前区间的左端点大于cur说明中间有缝隙不能合并将当前段的长度加入答案并重置新段为当前区间。否则说明当前区间与当前段有重叠或恰好相接。循环结束后将最后一段的长度累加。输出打印最终总长度。正确性基于排序后贪心合并每次遇到不重叠区间就结算当前段保证每个点只被计数一次最终得到所有区间覆盖的并集总长度。边界处理当N1时循环不会执行直接输出cur-cul1正确。当区间有包含关系时cur max(cur, a[i].r)能正确扩展右端点。数据范围使用long long避免溢出。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}