b870: Wickerbottom
Tags :
Accepted rate : 40人/45人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-10-04 19:25

Content

威克伯頓是長期住在孤島上的圖書館管理員,已經熟悉這個孤島的她看過許多冒險者在孤島上探險,其中有戰勝險惡環境成功脫困者,也有不少死於惡劣環境的戰敗者。在孤島上一年只有72天,依序為秋、冬、春、夏,其中秋季和春季分別有20天,冬季和夏季分別有16天,雖然冬季和夏季比較短,但也足以毀滅冒險者的生存意志。其中在夏天的時候所有可燃的物品都會因為高溫而燒起來,最後變成灰燼。威克伯頓最寶貝的樺木大道在每一個夏天都面臨自燃的危機,隨著大道的拓展,威克伯頓不得不新建許多滅火器,搶在自然的第一刻將火熄滅,大道上的樹彼此之間隔著不一樣的距離,威克伯頓能夠建造的滅火器有限,因此她希望能夠讓離滅火器和樺木樹之間的距離最大值愈小愈好,樺木樹和滅火器的距離定義為樺木樹距離最近滅火器的距離,現在給你樹的位置和能夠興建的滅火器數量,找出樺木樹和滅火器間距離最大值的最小可能。

滅火器只能興建在樺木大道的非負整數單位點上,一個點可以有多個樺木樹和滅火器。

Input

第一行有一個整數T(T≤5)代表有幾筆測試資料,每筆測試資料第一行有兩個正整數N,K,表示有N棵樹和能夠興建K(1≤K≤N)座滅火器,下一行有N個非負整數(<109)代表每一顆樺木樹的座標 

20%測資滿足
1≤N≤15
0≤樺木樹座標<20
 
40%測資滿足
1≤N≤1000
 
100%測資滿足
1≤N≤100000
Output

每筆測試資料輸出一行包含一個整數,代表樺木樹和滅火器間距離最大值的最小可能

Sample Input
2
5 3
4 3 1 9 15
5 3
4 3 1 15 9
Sample Output
2
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
Hint :

第一筆範例輸入:

滅火器興建在座標3, 9, 15,距離最大直為2,是所有方案中最小的

Tags:
出處:
105學年度板橋高中校內資訊學科能力競賽(三) [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」