题目概述

我们要求找到一个“中心”序列 B，使得 k 个给定序列到 B 的最大曼哈顿距离最小化。

形式化定义：

• 给定 k 个长度为 n 的序列 A₁, A₂, ..., Aₖ
• 定义序列间的距离：d(A,B) = Σ|aᵢ - bᵢ|
• 目标：找到序列 B，使得 max{d(Aᵢ,B)} 最小

问题分析

关键观察

1. 维度独立性：曼哈顿距离在各个维度上是独立的，问题可以分解为对每个位置独立求解
2. k ≤ 5 的特殊性：序列数量很少，这启发了特殊的解法
3. 中位数的性质：对于单个位置，如果只考虑一个序列集合，中位数能最小化绝对偏差和

难点

• 不能简单地对每个位置取中位数，因为需要保证整个序列 B 同时对所有 k 个序列都友好
• 需要在所有位置上进行协调，使得最大距离最小化

算法思路

特殊情况 k=2

当只有两个序列时，问题有简单解法：

• 总距离 s = Σ|a₁ᵢ - a₂ᵢ|
• 目标距离为 ⌈s/2⌉
• 构造方案：按位置逐个分配差值，保证总距离不超过目标

一般情况 (k=3,4,5)

核心算法采用二分答案 + 可行性检查：

1. 预处理：

   • 将 k 补足到 5（重复最后一个序列）
   • 对每个位置，计算以中位数（第3小的数）为基准时各序列的贡献
   • 统计各种配对关系下的可调整量

2. 二分搜索：

   • 在 [0, 1e15] 范围内二分最小可能的最大距离
   • 用 chk(mid) 判断是否存在方案使得所有距离 ≤ mid

3. 可行性检查 (chk函数)：

   • 检查三种主要情况：
     • 情况1：检查三个关键序列的组合能否通过调整满足约束
     • 情况2：处理单个序列距离过大的情况
     • 利用预计算的可调整量进行流量分配

4. 构造方案：

   • 根据二分得到的最小值和调整量
   • 对每个位置，从初始中位数出发，按照预分配的调整量进行微调
   • 保证全局约束满足

复杂度分析

• 时间复杂度：O(n log k + log(1e15) × C(k))，其中 C(k) 是 k 的常数函数
• 空间复杂度：O(nk)

关键技巧

1. 维度独立处理：虽然问题需要整体协调，但算法仍然利用了维度独立的性质
2. 中位数基准：以中位数作为初始解，然后进行微调
3. 调整量预计算：预先计算各位置可调整的范围，便于快速验证
4. 二分答案：将优化问题转化为决策问题

代码实现要点

// 核心步骤：
1. 读入数据，处理 k=2 的特殊情况
2. 将 k 补足到 5，统一处理
3. 预处理每个位置的中位数和可调整量
4. 二分搜索最小最大距离
5. 根据最优解构造输出序列

总结

这道题结合了：

• 曼哈顿距离的性质
• 中位数的优化特性
• 二分答案的框架
• 组合约束的满足

通过巧妙的预处理和调整策略，在 O(n log MAX) 时间内解决了这个看似复杂的问题，充分体现了对问题结构的深入理解和算法设计的巧妙性。