Try   HackMD

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

日期:2025年1月21日
作者:王一哲
ZeroJudge 題目連結

題目

問題描述

n 個人在一個數線上,他們的位置座標分別為
x1,x2,,xn
。今天要從
n
個人中選出
2k
個人開兩場會議,每一場會議要恰好
k
個人參與,並且每一個人最多只能參與一個會議。

若一個人位在

x,欲前往
y
處開會需要移動距離
|xy|
。請求出安排這兩場會議,使得參與會議的人移動距離總和最小值為何。

輸入說明

第一行輸入兩個數字

n,k (2kn2×105),接下來輸入
n
個非負整數,座標範圍不超過
109

子題配分

  • 30%:
    n100
  • 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
x1,x2,,xn
之中的值。如果要取
k
個人計算移動總距離最小值,則這
k
個人一定在附近,集合地點一定在他們的中間。所以解題時先將
x1,x2,,xn
由小到大排序。假設取
xi,xi+1,,xi+k1
計算移動總距離最小值,先找出中位數索引值
mid=i+k//2=i+m

若中位數
xmid=xi+m
,則中位數左側的人距離為
xmidxi<mid
,右側的人距離為
xi>midxmid
,總距離為

d=(xmidxi)+(xmidxi+1)++(xmidxmid1)+(xmid+1xmid)+(xmid+2xmid)++(xi+k1xmid)=(xi+xi+1++xm1)+(xm+1+xm+2++xi+k1)

如果用滑動視窗解題,固定視窗範圍為

(left,right]=(left,left+k]
left
是左端出界的索引值,寬度固定為
k
,則視窗滑動時,只要處理左、右兩端及中位數兩側的變化,將原來的總距離
d
改為
d+xleftxleft+mxleft+km+xleft+k

Python 程式碼

費時最久約為 0.9 s,使用記憶體最多約為 40 MB,通過測試。

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,通過測試。

#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:APCSPythonC++