该问题涉及任意数量的骰子，每个骰子的面数都是任意的。然后我们找到可以放在顺子中的最大骰子数量，参见Google 的 Code Jam 解释 https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a46471。实施应该在大约10^5骰子，每个骰子最多有10^6 sides.
我一直在尝试解决 Haskell 中的问题，这就是我的解决方案。但是，它的速度不够快，无法在该问题上获得满分，因此可以对此进行优化吗？
import Data.List (sort)
import Data.Foldable (foldl')
getMaxStraight :: [Int] -> Int
getMaxStraight sides =
foldl'
(\maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight)
0
(sort sides)
-- Doing IO in Haskell
-- Assuming the above works perfectly, something might not perform well below
main :: IO ()
main = do
line <- getLine :: IO String
let numberOfCases = read line :: Int
in mapM_ solveCase [1 .. numberOfCases]
solveCase :: Show a => a -> IO ()
solveCase i = do
line1 <- getLine :: IO String
line2 <- getLine :: IO String
let numberOfDice = read line1 :: Int
let diceSides = map read (words line2) :: [Int]
let maxStraight = getMaxStraight diceSides
putStrLn $ "Case #" ++ show i ++ ": " ++ show maxStraight
除此之外，我还编写了一个确实能及时运行的 Python 解决方案。我预计 Haskell 会比 Python 运行得更快。到底是怎么回事？
def get_max_straight(sides):
max_straight = 0
for side in sorted(sides):
if side > max_straight:
max_straight += 1
return max_straight
# Doing IO in Python
# This works as needed
if __name__ == '__main__':
tests_len = int(input())
for case_num in range(1, 1 + tests_len):
input() # Discard unneeded input
sides = [int(s) for s in input().split(' ')]
print(f'Case #{case_num}: {get_max_straight(sides)}')
None
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
