T30919: 猫猫去旅行

Heap, Math, http://cs101.openjudge.cn/practice/30919/

猫猫要去旅行。

在一条长为 L 的街道上有 n 处景点，第 i 处位于 x_i。猫猫的旅行计划一共有 i 天，每天要从住处去第 i 处景点。猫猫准备在街道上选择两个地方 s1,s2 住，并且在第 t 天晚上从 s1 搬去 s2（当然猫猫也可以不搬）。猫猫要使得自己每天往返景点的距离之和

$2 \times (\sum_{i = 1}^{t} | x_{i} - s_{1} | + \sum_{i = t + 1}^{n} | x_{i} - s_{2} |)$

最短。问这个距离是多少。

输入

第一行包含一个整数 $n$ （ $1 \leq n \leq 5 \times 10^{5}$ ），表示房屋数目。

第二行包含 $n$ 个整数 $x_{i}$ （ $1 \leq x_{i} \leq 10^{9}$ ），两两互不相同，表示每天要去的位置。

输出

输出一个整数，表示最短距离。

样例输入

9
3 4 1 9 2 12 6 5 7

样例输出

提示：

1、Heap, Math（堆，数学） 2、共 50 个测试点，单个测试点输入不超过 5MB，总输入不超过 120MB。

来源：2026 spring, RainFestival

为了解决这个问题，我们需要在街道上选择两个住处 $s_{1}, s_{2}$ 和一个搬家的时间 $t$ （ $0 \leq t \leq n$ ），以最小化猫猫每日往返景点的总距离。

根据绝对值不等式的性质，对于给定的天数区间，要使往返景点的距离之和最小，住处的位置应当选择为这些天所去景点位置的中位数。

定义：

$L (t)$ 为前 $t$ 天景点位置的中位数对应的最小绝对偏差和。
$R (t)$ 为后 $n - t$ 天（即第 $t + 1$ 到 $n$ 天）景点位置的中位数对应的最小绝对偏差和。

则我们需要计算出所有的 $L (t)$ 和 $R (t)$ ，并找出使 $L (t) + R (t)$ 最小的 $t$ 。通过双堆（一个大顶堆维护较小的一半元素，一个小顶堆维护较大的一半元素）可以动态地在 $O (n \log n)$ 的时间内求出所有前缀和后缀的中位数偏差和。

Python 代码

python

import sys
import heapq

def solve():
    # 快速读取输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    x = [int(v) for v in input_data[1:n+1]]
    
    # 预分配数组
    L = [0] * (n + 1)
    D = [0] * (n + 1)
    
    heappush = heapq.heappush
    heappop = heapq.heappop
    
    # 1. 计算前缀偏差和 L
    left = []
    right = []
    sum_left = 0
    sum_right = 0
    
    if n > 0:
        val = x[0]
        heappush(left, -val)
        sum_left = val
        L[1] = 0
        
    for i in range(1, n):
        val = x[i]
        if val <= -left[0]:
            heappush(left, -val)
            sum_left += val
        else:
            heappush(right, val)
            sum_right += val
            
        len_l = len(left)
        len_r = len(right)
        if len_l > len_r + 1:
            moved = -heappop(left)
            sum_left -= moved
            heappush(right, moved)
            sum_right += moved
            len_l -= 1
            len_r += 1
        elif len_r > len_l:
            moved = heappop(right)
            sum_right -= moved
            heappush(left, -moved)
            sum_left += moved
            len_l += 1
            len_r -= 1
            
        L[i + 1] = sum_right - sum_left - left[0] * (len_l - len_r)
        
    # 2. 计算后缀偏差和 D (对反转数组运行相同逻辑)
    left = []
    right = []
    sum_left = 0
    sum_right = 0
    x_rev = x[::-1]
    
    if n > 0:
        val = x_rev[0]
        heappush(left, -val)
        sum_left = val
        D[1] = 0
        
    for i in range(1, n):
        val = x_rev[i]
        if val <= -left[0]:
            heappush(left, -val)
            sum_left += val
        else:
            heappush(right, val)
            sum_right += val
            
        len_l = len(left)
        len_r = len(right)
        if len_l > len_r + 1:
            moved = -heappop(left)
            sum_left -= moved
            heappush(right, moved)
            sum_right += moved
            len_l -= 1
            len_r += 1
        elif len_r > len_l:
            moved = heappop(right)
            sum_right -= moved
            heappush(left, -moved)
            sum_left += moved
            len_l += 1
            len_r -= 1
            
        D[i + 1] = sum_right - sum_left - left[0] * (len_l - len_r)
        
    # 3. 寻找最优分割点 t
    min_dist = float('inf')
    for t in range(n + 1):
        val = L[t] + D[n - t]
        if val < min_dist:
            min_dist = val
            
    # 如果 OJ 要求的输出包含公式中的系数 2，则输出 2 * min_dist
    # 如果 OJ 存在描述与数据不符的情况（即样例输出为 18），则此处改为 print(min_dist)
    print(2 * min_dist)

if __name__ == '__main__':
    solve()

T30919: 猫猫去旅行 ​

T30919: 猫猫去旅行