CF1666E 题解

这题可以把分配方案改写成“分割点”问题。设整段是[ 0 , l ] [0,l][0,l]定义分割点0 x 0 x 1 ⋯ x n l 0x_0x_1\cdotsx_nl0x0​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[dL,\ uR]xi​∈[dL,uR]再与“必须包含第i ii个房子、且不能越过下一个房子位置”取交集。如果某一步交集为空就不可行全部走完且能到达x n l x_nlxn​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 ∗ LL^*LL∗的可行集合”一定有交集在这个交集里再取最小可行R RR就等价于最小化max ⁡ − min ⁡ \max-\minmax−min。得到一组满足要求的最优上下界后再跑一次check(L,R)并记录每一步可行区间。3. 构造具体答案先把最后一个分割点定为x n l x_nlxn​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​]。