題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🌈 AWC0104C Deciding the Meeting Place

Problem Statement

題目簡述

有 $N$ 個朋友位於數線上的整數座標 $A_i$ ，要選一個整數座標 $T$ 作為集合地點。每次操作可以讓某位朋友往左或往右走一格，移動成本為 $|A_i-T|$ 。

數線上有 $M$ 個禁止點 $B_j$ ，任何朋友在移動過程中、起點以外的途中位置、以及目的地都不能位於禁止點。若某個禁止點位於朋友起點與目的地之間，該朋友就無法抵達。

請在所有人都能抵達的合法集合地點中，最小化總移動成本；若不存在這樣的地點，輸出 $-1$ 。

Constraints

約束條件

$1 \le N \le 2 \times 10^5$
$0 \le M \le 2 \times 10^5$
$-10^9 \le A_i \le 10^9$
$-10^9 \le B_j \le 10^9$
$A_i \ne B_j$
$A_i$ 可以重複
所有 $B_j$ 互不相同
所有輸入皆為整數

思路：中位數貪心

先忽略禁止點的限制，本題等同於「給定數線上若干個點，選一個整數座標 $T$ ，使其他點到它的距離和最小」。

我們可以發現，如果我們把所有數字都變成中位數，那麼所需花費最小，可以由以下兩種方法來證明。

若 $n$ 為奇數，則中位數為 $nums[\lfloor \frac{n}{2} \rfloor]$ ，將所有數變成 $nums[\lfloor \frac{n}{2} \rfloor]$ 的代價最小。
若 $n$ 為偶數，則不管取 $[\,nums[\lfloor \frac{n}{2} \rfloor - 1],\ nums[\lfloor \frac{n}{2} \rfloor]\,]$ 之間的任意數字都可以使代價最小。

證明方法一：配對消去法

把所有座標排序後，從數線兩端開始配對。最左與最右這一對，不管集合地點選在哪裡，只要選在它們之間，這一對的總距離都是固定的；若選到區間外，總距離只會變大。

所以可以一層一層刪掉最左與最右。最後留下的就是中位數：

若 $n$ 為奇數，最小值在 $nums[\lfloor \frac{n}{2} \rfloor]$ 取得。
若 $n$ 為偶數，任取 $[\,nums[\lfloor \frac{n}{2} \rfloor - 1],\ nums[\lfloor \frac{n}{2} \rfloor]\,]$ 內的整數都能取得最小值。

證明方法二：離散差分證明

設排序後的座標為 $x_0 \le x_1 \le \cdots \le x_{n-1}$ ，令

f(t)=\sum_{i=0}^{n-1}|x_i-t|.

考慮把集合地點從 $t$ 移到 $t+1$ 時，代價的變化量：

f(t+1)-f(t) = \#\{i:x_i\le t\} - \#\{i:x_i>t\}.

當 $t$ 在中位數左側時，右側點數更多，差分為負，往右移會讓代價下降；當 $t$ 在中位數右側時，左側點數更多，差分為正，往右移會讓代價上升。

因此 $f(t)$ 先不增後不減，最小值出現在中位數位置。若 $n$ 為偶數，兩個中位數之間的整數位置都能取得相同最小值。

方法一：排序 + 雙指標分組

先看可行性的本質。在一維數線上，禁止點不能跨越，這等價於把數線切成若干個連通區間。兩個朋友如果被某個禁止點隔開，不管集合地點選在哪裡，至少有一方必須跨過禁止點，所以不可能一起到達。反過來，只要所有朋友都在同一個連通區間內，就可以在這段裡選集合地點，接著再套中位數貪心。

因此問題就變成了「將所有朋友分組，每組內都是連通的，且任意兩組之間存在禁止點隔開」。若只有一段，則在該段內取中位數就是答案。

如何判斷所有朋友落在幾個連通區間？

把朋友座標 $A_i$ 和禁止點 $B_j$ 都排序。接下來用雙指標掃描：一個維護目前處理到的朋友位置，另一個維護目前位置右側的第一個禁止點。

在實作中，可以用 $i$ 表示目前尚未分組的朋友下標，用 $j$ 表示目前考慮的禁止點下標。每次固定一個區間時，先讓 $j$ 移到第一個滿足 $B_j \ge A_i$ 的位置，此時 $B_j$ 就是目前區間右側的牆；接著把所有滿足 $A_i < B_j$ 、且尚未分組的朋友放進同一段，然後繼續往右掃描，直到所有朋友都被分配完為止。

這樣做的好處是能直接知道朋友被分成了幾段，且每段有哪些朋友（其實是我一開始看錯題目了QwQ）。不過本題只需要判斷段數是否為 $1$ ：超過一段就無解；若只有一段，在該段內取中位數就是答案。

可能的變形題目

雙指標分組的寫法不止適用於判斷可行性。如果題目變形成「每段各自求最小距離和，再取最優的段」，也能直接套用。

複雜度分析

時間複雜度： $\mathcal{O}(N \log N + M \log M)$ ，排序後雙指標線性掃描。
空間複雜度： $\mathcal{O}(N)$ ，需要保存分段結果；若只記錄段數，也可以降到 $\mathcal{O}(1)$ 額外空間。

方法二：直接判斷中位數模型是否可用

方法一會把所有連通區間實際切出來。不過對這題來說，我們只需要判斷一件事：所有朋友是否位於同一個可達區間。

排序朋友座標後（也可以直接取最小值和最大值，不過求中位數本身就需要排序），最左與最右位置決定了所有朋友的整體跨度。若存在某個禁止點滿足

\min A_i \le B_j \le \max A_i,

它就會把這段跨度切開。由於朋友座標不會等於禁止點，這個禁止點必然把朋友分到左右兩側；若要聚到同一點，至少有一側必須跨過禁止點，因此無解。

反過來，如果沒有禁止點落在這段跨度內，所有朋友之間就沒有阻隔，可以直接套用中位數貪心。此時選排序後的中位數，答案就是所有朋友到它的距離和。

複雜度分析

時間複雜度： $\mathcal{O}(N \log N + M)$ ，排序朋友座標後，線性檢查所有禁止點。
空間複雜度： $\mathcal{O}(1)$ 額外空間，不計輸入陣列。

Code

方法一：雙指標分組，每段獨立處理

from math import inf


def solve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    if m > 0:
        B = list(map(int, input().split()))
    else:
        B = []
    assert len(A) == n and len(B) == m

    A.sort()
    B.sort()
    B.append(inf)

    i = j = 0
    groups = []
    while i < n:
        group = []
        while B[j] < A[i]:
            j += 1
        while i < n and A[i] < B[j]:
            group.append(A[i])
            i += 1
        groups.append(group)

    if len(groups) > 1:
        print(-1)
    else:
        g = groups[0]
        k = len(g)
        mid = g[k // 2]
        ans = sum(abs(x - mid) for x in g)
        print(ans)


if __name__ == "__main__":
    solve()

方法二：直接判斷中位數模型是否可用

def solve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    if m > 0:
        B = list(map(int, input().split()))
    else:
        B = []
    assert len(A) == n and len(B) == m

    A.sort()

    for b in B:
        if A[0] <= b <= A[-1]:
            print(-1)
            return

    mid = A[n // 2]
    ans = sum(abs(x - mid) for x in A)
    print(ans)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @Rosuuri. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.