APCS實作題2025年1月第4題：分組開會

# APCS實作題2025年1月第4題：分組開會 > 日期：2025年1月21日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=q184) ## 題目 ### 問題描述有 $n$ 個人在一個數線上，他們的位置座標分別為 $x_1, x_2, \dots, x_n$。今天要從 $n$ 個人中選出 $2k$ 個人開兩場會議，每一場會議要恰好 $k$ 個人參與，並且每一個人最多只能參與一個會議。若一個人位在 $x$，欲前往 $y$ 處開會需要移動距離 $|x-y|$。請求出安排這兩場會議，使得參與會議的人移動距離總和最小值為何。 ### 輸入說明第一行輸入兩個數字 $n, k~(2k \leq n \leq 2 \times 10^5)$，接下來輸入 $n$ 個非負整數，座標範圍不超過 $10^9$。子題配分 - 30%：$n \leq 100$ - 70%：無限制 ### 輸出格式輸出安排這兩場會議，使得參與會議的人移動距離總和最小值為何。 ### 範例輸入1 ``` 6 2 5 2 0 6 9 6 ``` ### 範例輸出1 ``` 2 ``` ### 範例輸入2 ``` 7 3 6 3 2 2 0 9 8 ``` ### 範例輸出2 ``` 4 ``` ## 分析題目本題的說明似乎不太清楚，看起來開會的地點應該是在某個人所在的位置，所以題目中的 $y$ 是 $x_1, x_2, \dots, x_n$ 之中的值。如果要取 $k$ 個人計算移動總距離最小值，則這 $k$ 個人一定在附近，集合地點一定在他們的中間。所以解題時先將 $x_1, x_2, \dots, x_n$ 由小到大排序。假設取 $x_i, x_{i+1}, \dots, x_{i+k-1}$ 計算移動總距離最小值，先找出中位數索引值 $$ mid = i + k//2 = i + m $$ 若中位數 $x_{mid} = x_{i+m}$，則中位數左側的人距離為 $x_{mid} - x_{i<mid}$，右側的人距離為 $x_{i>mid} - x_{mid}$，總距離為 $$ \begin{align*} d &= (x_{mid} - x_i) + (x_{mid} - x_{i+1}) + \dots + (x_{mid} - x_{mid-1})\\ &+ (x_{mid+1} - x_{mid}) + (x_{mid+2} - x_{mid}) + \dots + (x_{i+k-1} - x_{mid}) \\ &= -(x_i + x_{i+1} + \dots + x_{m-1}) + (x_{m+1} + x_{m+2} + \dots + x_{i+k-1}) \end{align*} $$ 如果用滑動視窗解題，固定視窗範圍為 $(left, right] = (left, left+k]$，$left$ 是左端出界的索引值，寬度固定為 $k$，則視窗滑動時，只要處理左、右兩端及中位數兩側的變化，將原來的總距離 $d$ 改為 $$ d + x_{left} - x_{left+m} - x_{left+k-m} + x_{left+k} $$ ## Python 程式碼費時最久約為 0.9 s，使用記憶體最多約為 40 MB，通過測試。 ```python= from collections import deque n, k = map(int, input().split()) # 共有 n 個人，每場會議要有 k 個人 x = sorted(list(map(int, input().split()))) # 每個人的位置，由小到大排序 m = k//2 # k 的一半 curr = -sum(x[:m]) + sum(x[m:k]) # 編號 0 ~ k-1 的人移動的距離總和 if k%2 == 1: curr -= x[m] # 如果 k 是奇數，第4行會多加上 x[m]，要扣掉 dp = [curr] # 以編號 k-1 ~ n-1 的人所在位置當作開會的位置，同組 k 個人移動的距離總和 minleft = ans = float('INF') # 第1組的最小值，答案 rhs = deque() # 第2組的最小值，可能會從左端出界 for left in range(n-k): # 依序取出界的左端點 left = 0 ~ n-k，找各種分組的距離，滑動視窗，寬度固定為 k curr = curr + x[left] - x[left+m] - x[left+k-m] + x[left+k] # 更新視窗內的移動總距離 dp.append(curr) # dp 加上新的移動總距離 if left >= k-1: # 開始可以取第2組 minleft = min(minleft, dp[left-k+1]) # 更新 minleft if left >= k: rhs.popleft() # 移除第2組左端出界的值 while rhs and curr <= rhs[-1]: rhs.pop() # 如果 rhs 還有資料而且 curr 小於等於 rhs 最後面的值，移除最後一項 rhs.append(curr) # curr 加入 rhs，最後一項一定是第2組的最小值 ans = min(ans, minleft + rhs[-1]) # 更新 ans print(ans) ``` ## C++ 程式碼費時最久約為 72 ms，使用記憶體最多約為 5.4 MB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <deque> #include <algorithm> #include <climits> typedef long long LL; using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; // 共有 n 個人，每場會議要有 k 個人 vector<LL> x (n); // 每個人的位置，輸入之後由小到大排序 for(int i=0; i<n; i++) cin >> x[i]; sort(x.begin(), x.end()); int m = k/2; // k 的一半 LL curr = 0; // 範圍內的人移動的距離總和 for(int i=0; i<m; i++) curr -= x[i]; // 編號 0 ~ k-1 的人移動的距離總和 for(int i=m; i<k; i++) curr += x[i]; if (k%2 == 1) curr -= x[m]; // 如果 k 是奇數，第4行會多加上 x[m]，要扣掉 vector<LL> dp = {curr}; // 以編號 k-1 ~ n-1 的人所在位置當作開會的位置，同組 k 個人移動的距離總和 LL minleft = LLONG_MAX, ans = LLONG_MAX; // 第1組的最小值，答案 deque<LL> rhs; // 第2組的最小值，可能會從左端出界 for(int left=0; left<n-k; left++) { // 依序取出界的左端點 left = 0 ~ n-k，找各種分組的距離，滑動視窗，寬度固定為 k curr = curr + x[left] - x[left+m] - x[left+k-m] + x[left+k]; // 更新視窗內的移動總距離 dp.push_back(curr); // dp 加上新的移動總距離 if (left >= k-1) { // 開始可以取第2組 minleft = min(minleft, dp[left-k+1]); // 更新 minleft if (left >= k) rhs.pop_front(); // 移除第2組左端出界的值 while(!rhs.empty() && curr <= rhs.back()) rhs.pop_back(); // 如果 rhs 還有資料而且 curr 小於等於 rhs 最後面的值，移除最後一項 rhs.push_back(curr); // curr 加入 rhs，最後一項一定是第2組的最小值 ans = min(ans, minleft + rhs.back()); // 更新 ans } } cout << ans << "\n"; return 0; } ``` --- ###### tags:`APCS`、`Python`、`C++`