「Measures」社交距离题解

问题分析

我们需要在数轴上安排 $N+M$ 个人，使得任意两人之间的距离至少为 $D$，并且最小化所有人的最大移动距离。

核心思路

使用线段树维护位置信息，通过巧妙的区间更新来跟踪最优解。

关键观察

1. 排序不变性：最优解中人员的相对顺序与初始位置的相对顺序相同
2. 线段树维护：维护每个位置对应的"偏移量"，通过区间更新计算最小时间

算法详解

1. 数据预处理

// 将所有人员位置排序并重新编号
for (int i = 1; i <= m; i++) {
    scanf("%d", &a[i]);
    v[i] = {a[i], i};
}
sort(v + 1, v + m + 1, cmp);
for (int i = 1; i <= m; i++)
    a[v[i].id] = i;

作用：将所有人的位置排序，并为每个位置分配一个排名，便于线段树操作。

2. 线段树设计

线段树节点维护：

• max：区间最大偏移值
• min：区间最小偏移值
• ans：区间内的最大冲突值（即需要调整的最大距离）
• flag：懒标记，用于区间更新
• f：标记区间是否包含人员

struct segment {
    int l, r, f;
    ll max, min, ans, flag;
} tree[N * 4];

3. 核心操作

插入新人员

for (int i = 1; i <= m; i++) {
    cha(1, 1, a[i] - 1, d, 0);      // 更新前面所有位置
    cha(1, a[i], a[i], v[a[i]].x, 1); // 插入当前人员
    
    if (i > n)
        print(tree[1].ans);         // 输出加入新人后的答案
}

逻辑解释：

• cha(1, 1, a[i]-1, d, 0)：将排名在当前人员之前的所有位置向右推 $D$ 单位
• cha(1, a[i], a[i], v[a[i]].x, 1)：在当前排名位置插入人员

4. 线段树操作

区间更新

void cha(int k, int x, int y, int v, int f) {
    if (tree[k].l > y || tree[k].r < x) return;
    if (tree[k].l >= x && tree[k].r <= y) {
        tree[k].f |= f;
        work(k, v);  // 区间加操作
        return;
    }
    pd(k);  // 下传懒标记
    cha(k * 2, x, y, v, f);
    cha(k * 2 + 1, x, y, v, f);
    pu(k);  // 上传信息
}

信息合并

void pu(int k) {
    tree[k].f = tree[k*2].f | tree[k*2+1].f;
    
    if (!tree[k*2+1].f) {
        // 只有左子树有人
        tree[k].max = tree[k*2].max;
        tree[k].min = tree[k*2].min;
        tree[k].ans = tree[k*2].ans;
    } else if (!tree[k*2].f) {
        // 只有右子树有人  
        tree[k].max = tree[k*2+1].max;
        tree[k].min = tree[k*2+1].min;
        tree[k].ans = tree[k*2+1].ans;
    } else {
        // 左右子树都有人
        tree[k].min = min(tree[k*2].min, tree[k*2+1].min);
        tree[k].max = max(tree[k*2].max, tree[k*2+1].max);
        tree[k].ans = max(tree[k*2].max - tree[k*2+1].min, 
                         max(tree[k*2].ans, tree[k*2+1].ans));
    }
}

关键公式：tree[k].ans = max(左最大-右最小, 左答案, 右答案)

这个公式计算了跨越左右子树的冲突值。

算法正确性

为什么这样能计算最小时间？

1. 偏移量表示：每个位置的 max 值表示该位置人员需要向右移动的距离
2. 冲突检测：左最大 - 右最小 检测相邻区域间的距离是否足够
3. 最优子结构：通过线段树合并，维护全局的最大冲突值

时间复杂度

• 预处理排序：$O((N+M)\log(N+M))$
• 每次插入：$O(\log(N+M))$
• 总复杂度：$O((N+M)\log(N+M))$

样例验证

样例1：N=2, M=1, D=2, a=[1,3], b=[2]

• 初始：位置1和3，距离为2（满足要求）
• 插入2：需要调整，最小时间为1

样例3：N=3, M=3, D=3, a=[3,3,3], b=[3,3,3]

• 所有人在同一位置
• 需要分散开，输出4.5, 6, 7.5

总结

本题的巧妙之处在于：

1. 问题转化：将社交距离问题转化为线段树上的区间维护问题
2. 偏移量跟踪：通过维护位置偏移量来计算最小调整时间
3. 懒标记优化：使用懒标记实现高效的区间更新
4. 冲突检测：通过跨区间比较检测距离冲突

这种"线段树 + 区间更新 + 冲突检测"的方法为解决这类动态调整问题提供了有效思路。