题解 P1824 【进击的奶牛】

HoshinoTented

2019-07-25 00:26:14

Solution

# 检验 二分答案中最重要的莫过于检验了 给定间隔 $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++` 优雅多了,写起来很舒服