# 检验
二分答案中最重要的莫过于检验了
给定间隔 $x$, 求 能否放下所有牛
```haskell
-- 询问 :: 给定间隔 -> 上一只牛的位置 -> 题目中的N -> 题目中的C -> 房间 -> 结果
ask :: Int -> Int -> Int -> Int -> [Int] -> Bool
ask _ _ _ 0 _ = True -- 如果所有的牛都安排完毕,直接返回 True
ask _ _ _ _ [] = False -- 如果隔间用完,返回 False (因为 c == 0 的情况以及被第一个模式匹配拦截下来了)
ask x last n c (room:rooms) = if room - last >= x then ask x room n (c - 1) rooms else -- 如果 当前隔间 - 上一只牛所在隔间 >= 给定间隔 则 将当前隔间作为 新的 上一只牛所在隔间,并且减少需要安排的牛的数量
ask x last n c rooms -- 否则继续循环
```
# 二分
很简单,把 `C` 的板子抄过来就好了(板子应该不用注释了吧。。)
```haskell
-- 二分答案 :: 左界限 -> 右界限 -> 最终答案 -> 题目中的N -> 题目中的C -> 房间 -> 结果
binaryAns :: Int -> Int -> Int -> Int -> Int -> [Int] -> Int
binaryAns left right ans n c rooms = if left > right then ans else
let mid = (left + right) `div` 2 in
if ask' mid then binaryAns (mid + 1) right mid n c rooms
else binaryAns left (mid - 1) ans n c rooms
where
ask' x = ask x (head rooms) n (c - 1) rooms
```
# 数据读入
`Haskell` 的数据读入一直让我觉得很烦。。毕竟没有 `C/C++` 的 `for循环`
```haskell
-- 读取数据 -> 迭代器 -> IO 结果
readData :: Int -> IO [Int]
readData 0 = return [] -- 如果全部读完,返回空列表
readData n = do
i <- read <$> getLine -- 读取当前数据
readData (n - 1) >>= \xs -> return $ i : xs -- 获取剩余的数据,并把新数据添加在开头
```
# 最终代码
```haskell
import Data.List (sort)
-- 询问 :: 给定间隔 -> 上一只牛的位置 -> 题目中的N -> 题目中的C -> 房间 -> 结果
ask :: Int -> Int -> Int -> Int -> [Int] -> Bool
ask _ _ _ 0 _ = True -- 如果所有的牛都安排完毕,直接返回 True
ask _ _ _ _ [] = False -- 如果隔间用完,返回 False (因为 c == 0 的情况以及被第一个模式匹配拦截下来了)
ask x last n c (room:rooms) = if room - last >= x then ask x room n (c - 1) rooms else -- 如果 当前隔间 - 上一只牛所在隔间 >= 给定间隔 则 将当前隔间作为 新的 上一只牛所在隔间,并且减少需要安排的牛的数量
ask x last n c rooms -- 否则继续循环
-- 二分答案 :: 左界限 -> 右界限 -> 最终答案 -> 题目中的N -> 题目中的C -> 房间 -> 结果
binaryAns :: Int -> Int -> Int -> Int -> Int -> [Int] -> Int
binaryAns left right ans n c rooms = if left > right then ans else
let mid = (left + right) `div` 2 in
if ask' mid then binaryAns (mid + 1) right mid n c rooms
else binaryAns left (mid - 1) ans n c rooms
where
ask' x = ask x (head rooms) n (c - 1) rooms
-- 读取数据 -> 迭代器 -> IO 结果
readData :: Int -> IO [Int]
readData 0 = return [] -- 如果全部读完,返回空列表
readData n = do
i <- read <$> getLine -- 读取当前数据
readData (n - 1) >>= \xs -> return $ i : xs -- 获取剩余的数据,并把新数据添加在开头
main :: IO ()
main = do
[n, c] <- map read . words <$> getLine :: IO [Int]
rooms <- sort <$> readData n -- 数据是无序的 ,需要排序
print $ binaryAns 0 (last rooms - head rooms) 0 n c rooms -- 这里其实还想对 last rooms 进行优化,毕竟 Haskell 的 last 要遍历整个列表
return ()
```
比较坑到我的是二分的范围,第一次 $right$ 选错成 $n$ 了,结果最后一个点 WA 了
~~还有一个是错把 `mid + 1` 写成 `left + 1`,`mid - 1` 写成 `right - 1`,导致 T 了好多点~~
还是感觉 `Haskell` 比 ~~垃圾~~`C/C++` 优雅多了,写起来很舒服