分組開會 題解｜APCS 2025 年 1 月高級 第 4 題

前置知識

這題是「排序＋前綴和」加上兩個要自己推的觀察，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 排序：sort(x.begin(), x.end()) 把座標由小到大排好，本題所有推論都建立在「排好序」之上。
• 前綴和：NTUCPC Guide〈前綴和與差分〉——先算好「前 \(i\) 個的總和」，一段連續的和就是兩個前綴和相減；吳邦一《AP325》第 1 章 P-1-6「最接近的區間和」用同一招把區間和的計算從 \(O(n^3)\) 降到 \(O(n^2)\)（教材 PDF 第 25～27 頁）。
• 中位數讓「距離總和」最小：《AP325》第 8 章 P-8-3「購物中心選位置」一開始就是數線版的證明——集合點往人多的那一邊移動，總距離一定變少，所以最好的位置是中位數（教材 PDF 第 279～281 頁，站上題目 ap325p803 是它的樹上版；Python 版第 8 章（I））。

簡潔題意

直線上有 \(n\) 個人，第 \(i\) 個人在位置 \(x_i\)（位置可以重複）。選出兩組、每組 \(k\) 人，一個人最多只能在一組，其餘的人不參加。每一組自己挑一個集合地點，組員各走到集合地點，付出的代價是走的距離。求兩組所有人走的距離總和最少是多少（\(1 \le k\)，\(2k \le n \le 2 \times 10^5\)，\(0 \le x_i \le 10^9\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(30\) 分）：\(n \le 100\)。
• 子題組 2（\(70\) 分）：無額外限制。

兩個觀察：集合點放中位數、每組是排序後連續的一段

觀察一：一組人的集合點放在中位數最省。 集合點左邊有 \(L\) 個人、右邊有 \(R\) 個人，把集合點往左移 \(1\)，總距離變化 \(R - L\)：左邊人多就往左移會變少，右邊人多就往右移會變少，移到兩邊一樣多（或差一個）為止——那就是中位數。\(k\) 是奇數時中位數是正中間那個人的位置；\(k\) 是偶數時中間兩個人之間任何位置都一樣省，程式裡直接取其中一個人的位置就好。所以一組人的費用＝每個人到中位數的距離和。

觀察二：把座標排好序之後，兩組各是連續的一段，而且不重疊。 兩步推出來：

• 兩組不會交錯。 設左組集合點 \(p \le\) 右組集合點 \(q\)。如果左組有個人 \(a\) 站在右組某個人 \(b\) 的右邊（\(b \le a\)），把這兩個人交換組別：原本走 \(|a - p| + |b - q|\)，交換後走 \(|b - p| + |a - q|\)，後者不會比較多（兩段距離「一遠一近」換成「兩個中等」，總長不增加）。一直交換到沒有交錯為止，左組的人全部在右組的左邊。
• 每一組中間不會夾著不參加的人。 如果左組最左和最右的人之間夾了一個不參加的 \(y\)：\(y\) 在中位數左邊就讓他取代最左那個人、在右邊就取代最右那個人——\(y\) 離中位數比被換掉的人近，費用不會變多。一直換到這組變成連續的一段；右組同理。

所以答案只要在「排序後的兩個不重疊、各長 \(k\) 的窗口」裡找（圖 1）。

先拿下 30 分：算每個窗口的費用，枚舉兩個不重疊的窗口

排序後，窗口 [l, l+k-1] 的中位數就是 x[l + k/2]，費用直接用迴圈加總每個人到它的距離。兩組就是兩個窗口 l、r，右邊那組的起點 r >= l + k 才不會重疊：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> x(n);
    for (long long &v : x) cin >> v;
    sort(x.begin(), x.end());

    // cost[l]：排序後第 l 到第 l+k-1 個人同一組、在中位數集合的距離總和
    vector<long long> cost(n - k + 1);
    for (int l = 0; l + k <= n; l++) {
        long long median = x[l + k / 2];
        cost[l] = 0;
        for (int t = l; t < l + k; t++) cost[l] += abs(x[t] - median);
    }

    long long best = LLONG_MAX;
    for (int l = 0; l + k <= n; l++)               // 左邊那組從第 l 個人開始
        for (int r = l + k; r + k <= n; r++)       // 右邊那組從第 r 個人開始，r >= l + k 才不重疊
            best = min(best, cost[l] + cost[r]);
    cout << best << '\n';
    return 0;
}

\(n \le 100\) 怎麼算都很快，子題組 1 的 \(30\) 分穩穩到手。\(n = 2 \times 10^5\) 時算費用要 \(O(nk)\)、枚舉兩個窗口要 \(O(n^2)\)：本站實測 \(k = 10^5\) 一筆 \(6.7\) 秒、\(k = 1\) 一筆 \(12\) 秒。

從 30 分到 100 分：前綴和算費用、前綴最小值配對

費用改用前綴和。 中位數 \(m\) 左邊有 \(m - l\) 個人，他們走過來的距離和＝\(x_m \times (m - l) -\)（這些人的座標和）；右邊的人同理反過來，座標和都用前綴和一減就有。每個窗口 \(O(1)\)。

配對改用前綴最小值。 固定右邊那組的起點 \(r\)，左邊那組的起點只要 \(\le r - k\) 都行，我們要的是這些窗口裡最便宜的；\(r\) 每往右一格，就多一個合法的左窗口 cost[r - k]，用一個變數一路記「到目前為止最便宜的左窗口」就好，不用回頭掃。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> x(n);
    for (long long &v : x) cin >> v;
    sort(x.begin(), x.end());

    vector<long long> pre(n + 1, 0);               // pre[i] = x[0] + ... + x[i-1]
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + x[i];

    // cost[l]：第 l 到第 l+k-1 個人同一組、在中位數集合的距離總和
    vector<long long> cost(n - k + 1);
    for (int l = 0; l + k <= n; l++) {
        int m = l + k / 2;                                                   // 中位數的位置
        long long left = x[m] * (m - l) - (pre[m] - pre[l]);                 // 左邊 m-l 個人走到中位數
        long long right = (pre[l + k] - pre[m + 1]) - x[m] * (l + k - m - 1);   // 右邊 l+k-m-1 個人走到中位數
        cost[l] = left + right;
    }

    long long best = LLONG_MAX, bestLeft = LLONG_MAX;   // bestLeft：起點 <= r-k 的窗口裡最便宜的
    for (int r = k; r + k <= n; r++) {                  // 右邊那組從第 r 個人開始
        bestLeft = min(bestLeft, cost[r - k]);          // 起點 r-k 的窗口剛好接在 r 前面，從現在起可以配
        best = min(best, bestLeft + cost[r]);
    }
    cout << best << '\n';
    return 0;
}

排序 \(O(n \log n)\)，其餘 \(O(n)\)；\(n = 2 \times 10^5\) 本站實測不到 \(0.1\) 秒。一組的費用最多 \(10^5\) 個人各走 \(10^9\)，\(10^{14}\) 遠超過 int，座標、前綴和、費用都要 long long。

測過再交：範例裡沒有 \(k = 1\)，也沒有「平均數和中位數不同」的局面

兩個範例的 \(k\) 都是 \(2\) 或 \(3\)、座標都很小。沒蓋到的：\(k = 1\)、全部同一個位置、沒排序又有重複的輸入、平均數和中位數不一樣的分布、先挑最便宜那組會吃虧的局面、值域極端。

六筆都親眼看過正確，這題就穩了。