回分類題庫
h124: B.薑餅人的新樂園
關鍵字: NPSC 2013 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 26 Times / 25 Users | Submit : 47 Times / 29 Users | Accepted rate : 86%
題目加入時間 : 2014-09-16 09:41

Content: 简体中文

架設好全新的基地台後,薑餅人們的生活變得更加方便,部落也漸漸地恢復往日的蓬勃氣象。有一天,薑餅人工程師小薑在維修基地台時收到了來自地底下的不明訊號。小薑分析出訊號出現的位置之後便帶著鏟子與水壺前往地底探險,在那裡小薑發現了一處巨大的巧克力熔岩池,身為一個熱愛巧克力的薑餅人,他開心地吃了個痛快並且把水壺裝滿才回家。

從探險回來的那天起,小薑便經常收到來自地底下不同地方的訊號,而小薑也經常在實地探訪的過程中發現各種大量的點心。小薑希望讓部落的其他人也能夠共享這些點心,因此他向薑餅長老提出了一項建設計畫,打造地下的點心樂園。在計畫中總共有 N 個有點心的地方分散在地下各處,為了降低建設樂園的成本,小薑打算把樂園分為 M 個園區。建設一個園區的成本是根據深度來計算的,假設園區內最深與最淺的深度分別為 Dmax 和 Dmin,則該園區的建設成本為Dmax − Dmin。小薑已經調查好了每個有點心的地方的深度,請你寫一個程式計算最小建設總成本是多少。 

Input:

輸入的第一行有一個正整數 T (T ≤ 40),代表測試資料的組數。

每一筆測試資料共有兩行。第一行有兩個整數 N, M (1 ≤ M ≤ N ≤ 50000),中間以一個空白隔開,代表計畫中有 N 個有點心的地方,並打算把樂園分為 M 個園區。

第二行有 N 個整數 Di (1 ≤ Di ≤ 109),各以一個空白隔開,代表第 i 個有點心的地方的深度。

Output:

對於每一筆測試資料請輸出一行,包含一個整數,表示建設樂園的最小總成本。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
5 2
9 7 6 2 1
5 3
9 7 6 2 1

Sample Output :

4
2

Hint :

[註腳]

  1. 薑餅人不會吃壞肚子。
  2. 有點心的地方,就是樂園。

Author :

NPSC 2013 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum