734 . 收費站設置

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-greedy

Description

在一條直線高速公路上，有 $n$ 個點可以設置收費站，這 $n$ 個點分別是 $a_1,a_2,\dots,a_n$，你想要選擇其中 $k$ 個不同的點設置收費站，並且兩個相鄰的收費站之間的最小距離越大越好。

Input Format

輸入第一行包含兩個整數 $n,k$，表示有幾個可以設置收費站的點和需要設置幾個收費站。

第二行有 $n$ 個整數 $a_1,a_2,\dots,a_n$，表示可以設置收費站的點。

  • $2 \leq k \leq n \leq 10^ 5$
  • $\forall i \neq j,\ a_i \neq a_j$
  • $1 \leq a_i \leq 10^ 9$

Output Format

輸出一個整數，表示相鄰收費站的最小間距最大可以是多少。

Sample Input 1

5 2
4 8 7 6 3

Sample Output 1

5

Sample Input 2

10 4
1 4 10 13 19 20 25 28 30 35

Sample Output 2

10

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1
1 1000 524288 65536 1
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
Submit
Back to Top