angry-children[HackerRank-angry-children] 题解

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)

发表评论

电子邮件地址不会被公开。 必填项已用*标注