题解：洛谷 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 KK
L 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

【核心思想】

1. 问题分析：给定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​。这是一个二分答案 + 贪心判定问题。

2. 算法选择：

   • 二分答案（Binary Search）：对最大可能的得分进行二分，将最优化问题转化为判定问题
   • 贪心策略（Greedy）：按右端点升序排序后，每次优先选择结束最早的布，确保留给后续布尽可能多的空间
   • 关键性质：按右端点排序后，若所有相邻选中布之间的距离≥ m i d \geq mid≥mid，则任意两块选中布之间的距离都≥ m i d \geq mid≥mid。因为对于i < j < k i < j < ki<j<k，d 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

3. 关键步骤：

   • 初始化：读取N NN（布的总数）、K KK（需要选出的数量）
   • 存储区间：读取每块布的[ L i , R i ] [L_i, R_i][Li​,Ri​]，存入数组a [ 1.. N ] a[1..N]a[1..N]
   • 按右端点排序：sort(a+1, a+n+1, 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 = 1，last = 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 = 0l=0，输出-1（无法选出K KK块）；否则输出l ll

4. 时间/空间复杂度：

   • 时间复杂度：O ( N log ⁡ N + N log ⁡ M A X ) O(N \log N + N \log MAX)O(NlogN+NlogMAX)，排序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)，存储区间数组

5. 二分答案 + 贪心判定的核心思想：

   • 最优化转判定：将"最大化最小距离"转化为"判断是否可以选择K KK块布使得最小距离≥ m i d \geq mid≥mid"
   • 贪心选择策略：按右端点排序后优先选择结束早的区间，为后续选择预留最大空间，这是区间调度问题的经典贪心策略
   • 关键性质转化：通过排序保证非相邻区间的距离一定不小于相邻区间的距离，从而只需判定相邻区间距离
   • 上中点取整：使用(l + r + 1) / 2取上中点，配合l = mid/r = mid - 1避免死循环
   • 适用于"最大化最小值"或"最小化最大值"类区间选择问题

【算法标签】

#普及 #整数二分

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;// 最大布的数量intn,k;// n: 布的总数, k: 需要选出的布的数量structNode{intl,r;// l: 区间左端点, r: 区间右端点}a[N];// 存储所有布的区间信息// 按右端点升序排序（贪心策略：优先选择结束早的区间）boolcmp(Node x,Node y){returnx.r<y.r;}// 检查：是否能选出至少 k 块布，使得任意两块相邻选中的布之间的距离 >= midboolcheck(intmid){intcnt=1;// 已选中的布的数量，默认先选第一块（右端点最小的）intlast=a[1].r;// 上一次选中的布的右端点for(inti=2;i<=n;i++){// 当前布的左端点与上一次选中的布的右端点的距离 >= mid// 即两块布不重叠且距离至少为 midif(a[i].l-last>=mid){cnt++;// 选中当前布last=a[i].r;// 更新 last 为当前布的右端点if(cnt>=k)// 已选出 k 块布，满足条件returntrue;}}returncnt>=k;// 判断最终是否选出了至少 k 块布}intmain(){cin>>n>>k;// 读入布的总数和需要选出的数量for(inti=1;i<=n;i++)cin>>a[i].l>>a[i].r;// 读入每块布的区间sort(a+1,a+n+1,cmp);// 按右端点升序排序// 二分查找最大可能的得分intl=0,r=1e9;// 答案范围：[0, 1e9]while(l<r){intmid=(l+r+1)/2;// 取上中点，防止死循环if(check(mid))l=mid;// mid 可行，尝试更大的得分elser=mid-1;// mid 不可行，缩小范围}if(l==0)// 如果最大得分仍为0，说明无法选出 k 块不重叠的布cout<<-1<<endl;elsecout<<l<<endl;// 输出最大可能的得分return0;}

【运行结果】

6 3 1 12 2 7 5 9 9 13 10 18 15 20 2