angry-children[HackerRank-angry-children] 题解
题意:给出一个序列,从序列中选k个元素,使序列最大值与最小值的差最小。
解法:排序后再对所有合理的i,比较a[i] 与 a[i+k]的差值,求其最小即可,时间花在排序上是,为O(NlogN)
import Data.List
main = do
line<-getLine
line<-getLine
let g = (read line::Int) -1
ctx <- getContents
let p = sort [read x::Int| x<-lines ctx]
print $ minVal (map dist (zip p (jump p g)))
jump :: [Int] -> Int ->[Int]
jump xs 0 = xs
jump xs s = jump (tail xs) (s-1)
dist :: (Int,Int)->Int
dist (x,y) = y-x
minVal :: [Int] -> Int
minVal (x:[]) =x
minVal (x:xs) = min x (minVal xs)