e165: 誰是小隊長
Tags :
Accepted rate : 5人/7人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-30 01:21

Content

n個標兵,站在一條直線上,位置為x1,…,xn,其中xi都是不同的整數。請從中決定k個小隊長,使得所有標兵至其最近的小隊長的距離(位置相差的絕對值)總和最短。請計算最短總距離。


Input

第一行輸入一正整數t(1≤t≤10)表示共有t筆測試資料。對每筆測試資料,第一列包含兩個整數n與k, n<=1000, k<=10。第二列包含n個整數Xi,所有Xi均在int範圍內。

Output

對每筆測試資料,輸出答案於單獨一列。

Sample Input
1
5 3
-1 0 2 7 9
Sample Output
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (40%): 1.0s , <1M
公開 測資點#2 (40%): 1.0s , <1M
Hint :
Tags:
出處:
[管理者:
fdhs105285 (不簡單的三角形)
]


ID User Problem Subject Hit Post Date
17716
rollfc (胖胖貓)
e165
p-Median Problem
105 2019-05-10 09:42