csp信奥赛C高频考点专项训练之贪心算法 --【区间贪心】线段覆盖题目描述现在各大 oj 上有n nn个比赛每个比赛的开始、结束的时间点是知道的。yyy 认为参加越多的比赛noip 就能考的越好假的。所以他想知道他最多能参加几个比赛。由于 yyy 是蒟蒻如果要参加一个比赛必须善始善终而且不能同时参加2 22个及以上的比赛。输入格式第一行是一个整数n nn接下来n nn行每行是2 22个整数a i , b i ( a i b i ) a_{i},b_{i}\ (a_{i}b_{i})ai​,bi​(ai​bi​)表示比赛开始、结束的时间。输出格式一个整数最多参加的比赛数目。输入输出样例 1输入 13 0 2 2 4 1 3输出 12说明/提示对于20 % 20\%20%的数据n ≤ 10 n \le 10n≤10对于50 % 50\%50%的数据n ≤ 10 3 n \le 10^3n≤103对于70 % 70\%70%的数据n ≤ 10 5 n \le 10^{5}n≤105对于100 % 100\%100%的数据1 ≤ n ≤ 10 6 1\le n \le 10^{6}1≤n≤1060 ≤ a i b i ≤ 10 6 0 \le a_{i} b_{i} \le 10^60≤ai​bi​≤106。AC代码#includebits/stdc.husingnamespacestd;constintN1e610;// 定义最大数据范围// 定义活动结构体s为开始时间e为结束时间structnode{ints,e;}a[N];// 自定义排序规则按结束时间升序排列boolcmp(node x,node y){returnx.ey.e;}intmain(){intn;cinn;// 读入所有活动的开始和结束时间for(inti1;in;i){cina[i].sa[i].e;}// 按结束时间升序排序便于贪心选择sort(a1,an1,cmp);intans1;// 至少可以参加第一个活动intnow1;// 当前最后参加的活动是第一个// 从第二个活动开始遍历for(inti2;in;i){// 如果当前活动的开始时间 已选活动的结束时间则选择该活动if(a[i].sa[now].e){ans;nowi;// 更新最后参加的活动为当前活动}}coutans;return0;}功能分析该程序解决了活动选择问题目标是找出不重叠的最大活动数量。采用贪心算法策略排序阶段将所有活动按结束时间升序排序。这样每次可以优先选择结束时间最早的活动为后续活动留出更多时间。选择阶段初始化选择第一个活动排序后最早结束的然后遍历剩余活动。若当前活动的开始时间不早于已选活动的结束时间则选择该活动并更新已选活动的指针。通过这种策略保证每一步选择都是局部最优最终得到全局最优解。该算法的时间复杂度主要由排序决定为O(n log n)适用于题目中的最大数据规模。各种学习资料助力大家一站式学习和提升#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;}