题目大意

有 $N+1$ 条领带（长度 $A_1, A_2, \ldots, A_{N+1}$）和 $N$ 个员工（原领带长度 $B_1, B_2, \ldots, B_N$）。CEO 先选择一条领带不使用，然后将剩余的 $N$ 条领带分配给 $N$ 个员工。每个员工的奇怪感为 $\max(a - b, 0)$，其中 $a$ 是新领带长度，$b$ 是原领带长度。整场派对的奇怪度为所有员工中最大的奇怪感。

要求对每个 $k$（CEO 选择第 $k$ 条领带时），求出可能的最小奇怪度 $C_k$。

问题分析

关键观察

1. 问题结构：对于每个 $k$，需要从 $N+1$ 条领带中排除第 $k$ 条，用剩余的 $N$ 条匹配 $N$ 个员工
2. 目标函数：最小化 $\max\limits_{i} \max(a_{\pi(i)} - b_i, 0)$，其中 $\pi$ 是匹配方案
3. 数据规模：$N \leq 2 \times 10^5$，需要高效算法

问题转化

定义员工 $j$ 佩戴领带 $i$ 的奇怪度为：

对于固定的 $k$（排除领带 $k$），我们需要找到匹配 $\pi$ 使得：

算法设计

方法一：二分答案 + 贪心验证

核心思想：对于每个 $k$，二分搜索最小奇怪度 $X$，验证是否存在匹配使得所有 $d(\pi(j), j) \leq X$。

步骤

1. 预处理：

   • 将 $A$ 数组排序（但要记录原始位置）
   • 将 $B$ 数组排序

2. 二分框架：

   • 对每个 $k$，在 $[0, \max(A)]$ 范围内二分
   • 检查是否存在匹配方案

3. 验证函数：

   • 排除第 $k$ 条领带后，将剩余的 $N$ 条领带与 $N$ 个员工匹配
   • 使用贪心策略：将最小的可用领带分配给最小的员工
   • 检查是否所有配对都满足 $A_i \leq B_j + X$

复杂度：$O(N \log N \log \max(A))$，可能超时

方法二：排序匹配 + 前后缀预处理

核心思想：通过一次排序和预处理，同时求出所有 $C_k$。

步骤

1. 排序处理：

   • 将 $A$ 数组排序，记录原始位置到排序位置的映射
   • 将 $B$ 数组排序

2. 最优匹配策略：

   • 当使用所有 $N+1$ 条领带时，最优匹配是将第 $i$ 大的领带分配给第 $i$ 大的员工
   • 排除一条领带时，匹配关系会局部调整

3. 前后缀预处理：

   • 定义 $pre[i] = \max\limits_{j=1}^i \max(A_j - B_j, 0)$（前缀最大奇怪度）
   • 定义 $suf[i] = \max\limits_{j=i}^N \max(A_{j+1} - B_j, 0)$（后缀最大奇怪度）
   • 当排除第 $k$ 条领带时，$C_k = \max(pre[k-1], suf[k])$

4. 特殊情况处理：

   • 当 $k=1$ 时，只考虑后缀
   • 当 $k=N+1$ 时，只考虑前缀

正确性分析

• 排除领带 $k$ 后，前 $k-1$ 条领带匹配前 $k-1$ 个员工
• 后 $N-k+1$ 条领带匹配后 $N-k+1$ 个员工
• 这种分割保持了排序后的最优性

方法三：双指针扫描

核心思想：通过一次扫描同时计算所有排除情况下的最小奇怪度。

步骤

1. 合并排序：

   • 将 $A$ 和 $B$ 合并考虑，但标记类型
   • 按值排序

2. 扫描过程：

   • 维护两个指针，分别表示当前考虑的领带和员工
   • 动态计算当前匹配的最大奇怪度

3. 结果记录：

   • 当遇到 $A$ 类型的元素时，记录如果排除该领带时的答案
   • 利用扫描过程中的信息快速计算

复杂度分析

方法二（推荐）

• 排序：$O(N \log N)$
• 前后缀计算：$O(N)$
• 总复杂度：$O(N \log N)$

方法一

• 每个 $k$：$O(N \log \max(A))$
• 总复杂度：$O(N^2 \log \max(A))$（直接实现）或 $O(N \log N \log \max(A))$（优化后）

实现细节

前后缀方法实现

// 伪代码
vector<int> calculate_C(int N, vector<int>& A, vector<int>& B) {
    // 记录原始位置
    vector<pair<int, int>> A_indexed;
    for (int i = 0; i <= N; i++) {
        A_indexed.push_back({A[i], i});
    }
    
    // 排序
    sort(A_indexed.begin(), A_indexed.end());
    sort(B.begin(), B.end());
    
    // 计算前缀最大值
    vector<int> pre(N + 2, 0);
    for (int i = 1; i <= N; i++) {
        pre[i] = max(pre[i-1], max(A_indexed[i-1].first - B[i-1], 0));
    }
    
    // 计算后缀最大值
    vector<int> suf(N + 2, 0);
    for (int i = N; i >= 1; i--) {
        suf[i] = max(suf[i+1], max(A_indexed[i].first - B[i-1], 0));
    }
    
    // 计算答案
    vector<int> C(N + 1);
    for (int i = 0; i <= N; i++) {
        int original_pos = A_indexed[i].second;
        C[original_pos] = max(pre[i], suf[i+1]);
    }
    
    return C;
}

关键洞察

1. 排序不变性：最优匹配在排序后的序列中具有简单的结构
2. 独立性：排除一条领带将问题分成两个独立的子问题
3. 前后缀分解：通过预处理前后缀信息，可以 $O(1)$ 计算每个 $C_k$

算法选择建议

• 推荐方法二：前后缀预处理方法，复杂度最优，实现相对简单
• 小规模数据：方法一（二分答案）更直观易懂
• 大规模数据：必须使用方法二才能满足时间限制

总结

本题的核心在于发现排序后最优匹配的规律，以及通过前后缀预处理来高效处理所有可能的排除情况。这种"排序 + 前后缀"的思路在处理序列删除元素的相关问题时非常有效。

关键技巧：将原问题分解为前缀和后缀两个独立子问题，利用排序性质保证最优性。