007 - CP Classes（★3）

2025-10-05

問題

解答

提出 #69804189

type I = [[Int]]
type O = [[Int]]

solve :: I -> O
solve ([n]:xs:[q]:ys) = map (singleton . f) (concat ys)
    where
        ary = listArray (0,n-1) $ sort xs :: Array Int Int
        f b | idx == 0 = d
            | otherwise = min d d0
            where
                idx = lowerBound (ary!) (-1) (n-1) b
                idx0 = idx - 1
                d = abs (b - ary!idx)
                d0 = abs (b - ary!idx0)

Aiの列を昇順にソートした後に、各BjでAiの列を二分探索して、Ai>=Bjとなる最小のAiを求める。|Ai-Bj|と|A{i-1}-Bj|の小さいほうが、生徒jの不満度の最小値になる。

ライブラリに追加

lowerBound :: Ord a => (Int -> a) -> Int -> Int -> a -> Int
lowerBound f lb ub x
    | ub - lb > 1 = if f mid >= x
                    then lowerBound f lb mid x
                    else lowerBound f mid ub x
    | otherwise = ub
    where
        mid = (lb + ub) `div` 2

蟻本を参考に二分探索を追加した。探索範囲が(lb, ub]なのが今一つな気がする。今後探索範囲を[lb,ub)に変更したラッパーを書くかも。