q184. 4. 分組開會 - 高中生程式解題系統

內容

有 $n$ 個人在一個數線上，他們的位置座標分別為 $x_{1}, x_{2}, \dots, x_{n}$ 。今天要從 $n$ 個人中選出 $2 k$ 個人開兩場會議，每一場會議要恰好 $k$ 個人參與，並且每一個人最多只能參與一個會議。

若一個人位在 $x$ ，欲前往 $y$ 處開會需要 $| x - y |$ 。請求出安排這兩場會議，使得參與會議的人移動距離總和最小值為何。

輸入說明

第一行輸入兩個數字 $n, k (2 k \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

7 3
6 3 2 2 0 9 8

範例輸出 #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

標籤:

出處:

2025年1月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
45108	leeguanhan09 ... (李冠翰)	q184	Python 簡單詳解	476	2025-01-07 23:24
45055	ericshen1955 ... (暴力又被TLE)	q184	題解附詳細註解的 Python code	672	2025-01-05 19:20