题解：洛谷 AT_abc463_d [ABC463D] Maximize the Gap

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷AT_abc463_d [ABC463D] Maximize the Gap - 洛谷【题目描述】There areN NNcloths on a number line. Thei ii-th( 1 ≤ i ≤ N ) (1\le i\le N)(1≤i≤N)cloth covers the interval[ L i , R i ] \lbrack L _ i,R _ i\rbrack[Li​,Ri​]on the line. A point on the line may be covered by two or more cloths, or not covered by any cloth.Two cloths are said to overlap if some point on the line is covered by both of those cloths.For two cloths that do not overlap, define theirdistanceas follows:The minimum value of∣ p − q ∣ |p-q|∣p−q∣over all pointsp ppcovered by one cloth and all pointsq qqcovered by the other cloth.ForK KKcloths no two of which overlap, define theirscoreas the minimum distance among all pairs of those cloths. Find the maximum possible score when choosingK KKcloths from theN NNcloths so that no two of the chosen cloths overlap.If it is impossible to chooseK KKsuch cloths, output-1.数轴上有N NN块布。第i ii块( 1 ≤ i ≤ N ) (1\le i\le N)(1≤i≤N)布覆盖数轴上的区间[ L i , R i ] [L_i, R_i][Li​,Ri​]。数轴上的一个点可能被两块或更多块布覆盖也可能不被任何布覆盖。如果数轴上的某个点被两块布同时覆盖则称这两块布重叠。对于两块不重叠的布定义它们之间的距离如下一块布覆盖的所有点p pp与另一块布覆盖的所有点q qq之间∣ p − q ∣ |p-q|∣p−q∣的最小值。对于K KK块两两之间都不重叠的布定义它们的得分为这些布中所有两两组合之间的距离的最小值。请从N NN块布中选出K KK块两两不重叠的布使得得分最大。如果无法选出这样的K KK块布输出-1。【输入】The input is given from Standard Input in the following format:N NNK KKL 1 L _ 1L1​R 1 R _ 1R1​L 2 L _ 2L2​R 2 R _ 2R2​⋮ \vdots⋮L N L _ NLN​R N R _ NRN​【输出】Output the answer.【输入样例】6 3 1 12 2 7 5 9 9 13 10 18 15 20【输出样例】2【核心思想】问题分析给定N NN块布每块覆盖区间[ L i , R i ] [L_i, R_i][Li​,Ri​]。需要选出K KK块两两不重叠的布使得所有选中布之间两两距离的最小值最大化。两块不重叠布的距离定义为它们覆盖点之间∣ p − q ∣ |p-q|∣p−q∣的最小值即若布i ii在布j jj左侧且不重叠则距离为L j − R i L_j - R_iLj​−Ri​。这是一个二分答案 贪心判定问题。算法选择二分答案Binary Search对最大可能的得分进行二分将最优化问题转化为判定问题贪心策略Greedy按右端点升序排序后每次优先选择结束最早的布确保留给后续布尽可能多的空间关键性质按右端点排序后若所有相邻选中布之间的距离≥ m i d \geq mid≥mid则任意两块选中布之间的距离都≥ m i d \geq mid≥mid。因为对于i j k i j kijkd i s t ( i , k ) L k − R i ( L k − R j ) ( R j − R i ) ≥ d i s t ( j , k ) ≥ m i d dist(i,k) L_k - R_i (L_k - R_j) (R_j - R_i) \geq dist(j,k) \geq middist(i,k)Lk​−Ri​(Lk​−Rj​)(Rj​−Ri​)≥dist(j,k)≥mid关键步骤初始化读取N NN布的总数、K KK需要选出的数量存储区间读取每块布的[ L i , R i ] [L_i, R_i][Li​,Ri​]存入数组a [ 1.. N ] a[1..N]a[1..N]按右端点排序sort(a1, an1, cmp)按R i R_iRi​升序排列二分答案范围[ 0 , 10 9 ] [0, 10^9][0,109]取上中点mid (l r 1) / 2防止死循环若check(mid)为真说明得分≥ m i d \geq mid≥mid可行l mid否则r mid - 1判定函数check(mid)贪心选择初始化cnt 1last a[1].r先选右端点最小的布遍历i ii从2 22到N NN若a [ i ] . l − l a s t ≥ m i d a[i].l - last \geq mida[i].l−last≥mid当前布与上一块选中布的距离足够cnt选中当前布last a[i].r更新最后选中布的右端点若cnt k返回true返回cnt k输出答案若最终l 0 l 0l0输出-1无法选出K KK块否则输出l ll时间/空间复杂度时间复杂度O ( N log ⁡ N N log ⁡ M A X ) O(N \log N N \log MAX)O(NlogNNlogMAX)排序O ( N log ⁡ N ) O(N \log N)O(NlogN)二分O ( log ⁡ M A X ) O(\log MAX)O(logMAX)每次判定O ( N ) O(N)O(N)空间复杂度O ( N ) O(N)O(N)存储区间数组二分答案 贪心判定的核心思想最优化转判定将最大化最小距离转化为判断是否可以选择K KK块布使得最小距离≥ m i d \geq mid≥mid贪心选择策略按右端点排序后优先选择结束早的区间为后续选择预留最大空间这是区间调度问题的经典贪心策略关键性质转化通过排序保证非相邻区间的距离一定不小于相邻区间的距离从而只需判定相邻区间距离上中点取整使用(l r 1) / 2取上中点配合l mid/r mid - 1避免死循环适用于最大化最小值或最小化最大值类区间选择问题【算法标签】#普及 #整数二分【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;// 最大布的数量intn,k;// n: 布的总数, k: 需要选出的布的数量structNode{intl,r;// l: 区间左端点, r: 区间右端点}a[N];// 存储所有布的区间信息// 按右端点升序排序贪心策略优先选择结束早的区间boolcmp(Node x,Node y){returnx.ry.r;}// 检查是否能选出至少 k 块布使得任意两块相邻选中的布之间的距离 midboolcheck(intmid){intcnt1;// 已选中的布的数量默认先选第一块右端点最小的intlasta[1].r;// 上一次选中的布的右端点for(inti2;in;i){// 当前布的左端点与上一次选中的布的右端点的距离 mid// 即两块布不重叠且距离至少为 midif(a[i].l-lastmid){cnt;// 选中当前布lasta[i].r;// 更新 last 为当前布的右端点if(cntk)// 已选出 k 块布满足条件returntrue;}}returncntk;// 判断最终是否选出了至少 k 块布}intmain(){cinnk;// 读入布的总数和需要选出的数量for(inti1;in;i)cina[i].la[i].r;// 读入每块布的区间sort(a1,an1,cmp);// 按右端点升序排序// 二分查找最大可能的得分intl0,r1e9;// 答案范围[0, 1e9]while(lr){intmid(lr1)/2;// 取上中点防止死循环if(check(mid))lmid;// mid 可行尝试更大的得分elsermid-1;// mid 不可行缩小范围}if(l0)// 如果最大得分仍为0说明无法选出 k 块不重叠的布cout-1endl;elsecoutlendl;// 输出最大可能的得分return0;}【运行结果】6 3 1 12 2 7 5 9 9 13 10 18 15 20 2