CF1666E 题解
这题可以把分配方案改写成“分割点”问题。
设整段是[ 0 , l ] [0,l][0,l]，定义分割点：
0 = x 0 < x 1 < ⋯ < x n = l 0=x_0<x_1<\cdots<x_n=l0=x0<x1<⋯<xn=l
那么第i ii个人拿到区间[ x i − 1 , x i ] [x_{i-1},x_i][xi−1,xi]，并且要满足：
- 长度限制：L ≤ x i − x i − 1 ≤ R L \le x_i-x_{i-1}\le RL≤xi−xi−1≤R
- 包含房子：x i − 1 ≤ a i ≤ x i x_{i-1}\le a_i\le x_ixi−1≤ai≤xi
- 区间首尾相接且覆盖全段
目标是让最长与最短长度差最小，也就是尽量缩小R − L R-LR−L。
1. 可行性检查check(L,R)
从左到右维护“当前分割点x i x_ixi的可行范围”[ d , u ] [d,u][d,u]。
已知上一步x i − 1 ∈ [ d , u ] x_{i-1}\in[d,u]xi−1∈[d,u]，则当前点先由长度得到：
x i ∈ [ d + L , u + R ] x_i\in[d+L,\ u+R]xi∈[d+L,u+R]
再与“必须包含第i ii个房子、且不能越过下一个房子位置”取交集。
如果某一步交集为空，就不可行；全部走完且能到达x n = l x_n=lxn=l，就可行。
这个检查是线性的，复杂度O ( n ) O(n)O(n)。
2. 如何求最优的L , R L,RL,R
代码采用两次二分：
- 先二分最大的L LL（给很大的R RR，只看最短长度能有多大）；
- 固定这个L LL，再二分最小的R RR。
这一步的正确性可以这样理解：
- 记某个方案的最短段长为min \minmin，最长段长为max \maxmax，目标是最小化max − min \max-\minmax−min。
- 若一个最优方案的min \minmin不是“全局可行的最大值”，说明还可以把所有区间整体往更均衡方向推进，使最短段再增大而不破坏可行性，这与“最优”矛盾。
- 换句话说，最优解中一定存在一个方案，其最短段长取到可行上界L ∗ L^*L∗（也就是第一步二分出的最大L LL）。
- 因此最优解与“L = L ∗ L=L^*L=L∗的可行集合”一定有交集；在这个交集里再取最小可行R RR，就等价于最小化max − min \max-\minmax−min。
得到一组满足要求的最优上下界后，再跑一次check(L,R)并记录每一步可行区间。
3. 构造具体答案
先把最后一个分割点定为x n = l x_n=lxn=l，再从后往前回推：
- 保证与下一个分割点的距离仍在[ L , R ] [L,R][L,R]内；
- 保证每个x i x_ixi仍落在前面算出的可行区间内。
这样就能得到一组合法分割点x 1 , … , x n − 1 x_1,\dots,x_{n-1}x1,…,xn−1，进而输出所有区间
[ x i − 1 , x i ] [x_{i-1},x_i][xi−1,xi]。