TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

100.0% (21/21)

Submission's AC Ratio

46.6% (62/133)

Description

你知道郵差的辛苦嗎?

冒著風吹雨淋只為了替人們送達那名為信件的感動。

所以為了體恤郵差們的辛勞,郵局設置的位置成了一個重要的問題。

在一個世外桃源中,有一個名叫真新鎮的純樸小鎮,居民們快樂地生活在那裡。

不過由於過於安逸,為了避免麻煩,所有居民的家全部都在一條筆直的公路旁。並且鎮長家就在這條路的盡頭

雖然日子很悠閒,但由於小鎮過於龐大,卻又缺少郵局,所以每次信件都要仰賴隔壁鎮的郵差幫忙,讓人十分苦惱。

你是一個真新鎮的鎮長小智,正準備在鎮上的某幾個人家裡設置一個郵局(居民們都很樂意將自己家裡變成郵局,因為這是偉大的貢獻)

當然如果必要的話,你也很樂意在自己家設立郵局。

由於經費有限,你最多只能把 k 個人家改建成郵局。

但為了郵差的辛勞,所以你想要盡量讓每一戶人家到最近郵局的距離和最短。

Input Format

本題只有一筆測試資料:

第一行包含兩個正整數 n, k ,代表小鎮裡戶數有 n 戶(包含鎮長),並且你最多只能設立 k 個郵局
(0 < n, k <= 1000)

接下來有 n - 1 行,
每行有一個整數 ai,代表有一個居民的家與鎮長家距離為 ai
(0 < ai < 1,000,000,且ai兩兩不相同)

Output Format

請輸出一個整數,代表每一戶人家到最近郵局的距離和最短為多少。

Sample Input

5 1
1
2
3
4

Sample Output

6

Hints

以範例測資來說
最適宜放置的地點為第二戶人家
Dist=|0-2|+|1-2|+|2-2|+|3-2|+|4-2|=6

Problem Source

原TIOJ1449 / 建中校內培訓第二次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536
3 3000 65536 65536
4 3000 65536 65536
5 3000 65536 65536
6 3000 65536 65536
7 3000 65536 65536
8 3000 65536 65536
9 3000 65536 65536
10 3000 65536 65536