BZOJ-1150: [CTSC2007]資料備份Backup (貪心絕世好題)

1150: [CTSC2007]資料備份Backup

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 2560  Solved: 1032

[​​Submit​​​][​​Status​​​][​​Discuss​​]

Description

　　你在一家 IT 公司為大型寫字樓或辦公樓（offices）的計算機資料做備份。然而資料備份的工作是枯燥乏味

的，是以你想設計一個系統讓不同的辦公樓彼此之間互相備份，而你則坐在家中盡享計算機遊戲的樂趣。已知辦公

樓都位于同一條街上。你決定給這些辦公樓配對（兩個一組）。每一對辦公樓可以通過在這兩個建築物之間鋪設網

絡電纜使得它們可以互相備份。然而，網絡電纜的費用很高。當地電信公司僅能為你提供 K 條網絡電纜，這意味

着你僅能為 K 對辦公樓（或總計2K個辦公樓）安排備份。任一個辦公樓都屬于唯一的配對組（換句話說，這 2K 

個辦公樓一定是相異的）。此外，電信公司需按網絡電纜的長度（公裡數）收費。因而，你需要選擇這 K 對辦公

樓使得電纜的總長度盡可能短。換句話說，你需要選擇這 K 對辦公樓，使得每一對辦公樓之間的距離之和（總距

離）盡可能小。下面給出一個示例，假定你有 5 個客戶，其辦公樓都在一條街上，如下圖所示。這 5 個辦公樓分

别位于距離大街起點 1km, 3km, 4km, 6km 和 12km 處。電信公司僅為你提供 K=2 條電纜。

　　上例中最好的配對方案是将第 1 個和第 2 個辦公樓相連，第 3 個和第 4 個辦公樓相連。這樣可按要求使用

 K=2 條電纜。第 1 條電纜的長度是 3km-1km=2km ，第 2 條電纜的長度是 6km-4km=2km。這種配對方案需要總長

 4km 的網絡電纜，滿足距離之和最小的要求。

Input

　　輸入的第一行包含整數n和k，其中n（2 ≤ n ≤100 000）表示辦公樓的數目，k（1≤ k≤ n/2）表示可利用

的網絡電纜的數目。接下來的n行每行僅包含一個整數（0≤ s ≤1000 000 000）, 表示每個辦公樓到大街起點處

的距離。這些整數将按照從小到大的順序依次出現。

Output

　　輸出應由一個正整數組成，給出将2K個相異的辦公樓連成k對所需的網絡電纜的最小總長度。

Sample Input

5 2

1

3

4

6

12

Sample Output

HINT

Source