1632 . 快樂建造梯子
Description
傳說中, 在高天原上有一個樹朋友聚落,
這個聚落的樹朋友們很喜歡爬到別人的樹頂上,
當然, 他們也都很樂意讓別人爬到自家樹頂上.
然而隨著時間過去, 許多長得快的樹漸漸與其它樹拉開距離,
這使得樹朋友們要爬到這些樹頂上變得困難.
為此, 樹朋友們決定合力建造一個梯子來輔助爬樹.
對於某個樹對, 如果兩棵樹的高度差小於等於梯子長度, 則梯子就適用於這個樹對.
但因為高天原的樹朋友們非常有環保概念,
他們知道, 如果要讓梯子能夠適用於任兩個樹對, 必定會消耗掉太多資源.
所以他們決定, 這個梯子只需要能夠適用於 k 對樹對即可.
但, 這時問題就來了, 由於樹實在太多,
他們不知道如果要適用於 k 對樹對, 梯子至少要造到多長才行.
而碰巧他們得知了你會寫程式, 所以便求助於你.
你能夠幫助他們找出梯子至少要多長嗎?
Input Format
第一行有兩個數字 n, k. n 代表有幾棵樹.
第二行有 n 個數字, 代表每棵樹的高度.
(1 <= 每棵樹的高度 <= 2 * 109 )
(2 <= n <= 200000, 1 <= k <= C(n, 2))
你可以假設每棵樹高度不同.
Output Format
請輸出一個整數代表梯子至少要多長.
Sample Input 1
5 2
9 18 27 28 37
9 18 27 28 37
Sample Output 1
9
Hints
9雖然適用於4個樹對,
但8以下只能適用於1個樹對, 故選9.
另外, 梯子明明就是拿來從樹頂爬到另一個樹頂的,
為什麼在原圖中卻是從地面爬上去呢?
其實也是因為出題者畫完才發現, 所以也算了(?)
Problem Source
原TIOJ1632 / Problem Setter: worm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |