题解

问题分析

这是一个贪心 + 线段树维护前缀和的问题。圣诞老人需要在一条直线上收集礼物并分发给孩子，要求找到每个场景下的最短行走距离。

关键观察

1. 行走模式：圣诞老人先向右走到 $X_i$，然后向左走到 $xLeft_i$，总距离 $D_i = 2X_i - xLeft_i$
2. 礼物分配约束：孩子只能收到价值不低于其期望的礼物
3. 可行性条件：必须收集所有精灵的礼物，并且有足够的孩子能接收这些礼物

算法思路

双指针 + 线段树维护前缀和最小值：

数据结构设计

• SegmentTree：维护前缀和的最小值，用于检查可行性
• Info：存储区间和与前缀最小值
• multiset：存储可用的礼物价值

核心思想

1. 前缀和意义：对于每个价值 $v$，维护 f[v] = 收到的礼物数 - 分发的礼物数
2. 可行性判断：如果所有前缀和的最小值 $\geq 0$，说明礼物可以全部分发
3. 贪心分配：为孩子分配满足条件的最小价值的礼物

算法步骤

初始化阶段

// 转换H数组：精灵为-1，孩子为1
if (H[i] == 0) H[i] = -1;

右指针扩展

while (minr < N && (minr < rightGift || seg.rangeQuery(0, N + 1).premin < 0)) {
    minr++;
    if (minr < N) {
        f[V[minr]] += H[minr];  // 更新计数
        seg.modify(V[minr], f[V[minr]]);  // 更新线段树
    }
}

左指针移动与礼物分配

for (int l = 0, i = 0; l < N; l++) {
    // 处理相同位置的房屋
    while (j < N && X[j] == X[l]) j++;
    
    // 收集礼物
    for (int k = i; k < j; k++) {
        if (H[k] == -1) s.insert(V[k]);
    }
    
    // 分配礼物给孩子
    for (int k = i; k < j; k++) {
        if (H[k] == 1) {
            f[V[k]] -= H[k];  // 孩子期望值计数
            seg.modify(V[k], f[V[k]]);
            auto it = s.lower_bound(V[k]);  // 找最小满足条件的礼物
            if (it != s.end()) {
                int x = *it;
                s.erase(it);
                f[x] += 1;  // 礼物被分配
                seg.modify(x, f[x]);
            }
        }
    }
    
    // 更新答案
    while (minr < N && (X[minr] <= X[l] || seg.rangeQuery(0, N + 1).premin < 0)) {
        ans[minr] = 2 * X[minr] - X[l];  // 计算距离
        minr++;
        // 继续扩展右指针
    }
}

复杂度分析

• 线段树操作：$O(\log N)$ 每次修改和查询
• 双指针扫描：$O(N)$ 每个房屋被处理常数次
• multiset操作：$O(\log N)$ 每次插入和查找
• 总复杂度：$O(N \log N)$

关键技巧

1. 前缀和最小值检查：快速判断礼物是否能全部分发
2. 贪心分配：为孩子分配最小满足条件的礼物，最大化后续灵活性
3. 双指针维护：同时处理左边界和右边界的约束

样例验证

样例1场景7：

• 需要返回到 $xLeft_7 = 10$
• $D_7 = 2 \times 25 - 10 = 40$ ✓

样例1场景8：

• 无需返回，$xLeft_8 = 35$
• $D_8 = 2 \times 35 - 35 = 35$ ✓

算法标签

• 贪心算法
• 线段树
• 双指针
• 前缀和优化
• 区间维护
• 可行性判断