TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

95.7% (44/46)

Submission's AC Ratio

36.1% (122/338)

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

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
10 3000 65536 262144 11