将洗澡钱分发给n个人

Question

我在网上发现了以下问题，并且很想在 Haskell 中解决这个问题。

给定钱X泰铢和N个人，我们将把钱分配为 如下...第一回合：给第一个人1泰铢，第二个人 得到 2 泰铢，...，第 N 个人得到 N 泰铢。如果有钱（X - 分配的钱）还剩下，那么我们将分配它 再次。所以...第二回合：给第一个人2泰铢，第二个人 得到 3 泰铢，...，第 N 个人得到 N+1 泰铢。第三回合：给予 第一人3泰铢，第二人4泰铢，……，第N人 每人获得 N+2 泰铢。

我们将分发资金，直到用完为止。然后输出是一个 每个人得到的一系列钱。

例如：输入：x = 21（泰铢）和 n = 5（作为人头数）。第一名 回合，每个人都会收到钱作为

{1, 2, 3, 4, 5}

第二回合， 每个人都会收到钱

{2, 3, 1, 0, 0}

∴最终输出将是

{3, 5, 4, 4, 5}

问题是如何在 Haskell 中实现这一点，并且最好在 O(n) 时间内实现。

Answer 1

我们要解决的第一个问题是知道我们可以填满多少回合，以及我们还需要分配多少个巴斯。我们可以将其表达为求和表达式：

我们可以用它来表示 Bath 的 k 的数量，从而通过 M 获得整行的数量：

如果我们只考虑完整轮，第一个人将有M×(M+1)/2，第二人有M×(M+1)/2+M，以及j-第人 M×(M+1)/2+j×M.

有可能还剩下Bath的，确实，在M整轮之后，还剩下r = K - M×n×(m+n)/2，然后将这些分配到决赛中圆形的。这里 min(M+1, r)，第二个 min(M+2, max(r-M-1, 0))，第三个 min(M+3, max(r-2×M) -3, 0)) 等

如果我们假设所有算术运算都在 O(1) 中运行，那么以下算法在 O(n) 中运行：

distribute :: Int -> Int -> [Int]
distribute n k = zipWith (+) (take n [n0, n0 + m ..]) (final (m + 1) r)
  where
    m = (floor (sqrt (fromIntegral (8 * k * n + n * n * n * n) :: Double)) - n * n) `div` (2 * n)
    r = k - (m * n * (m + n) `div` 2)
    n0 = m * (m + 1) `div` 2

final :: Int -> Int -> [Int]
final i j = k : final (i + 1) (j - k)
  where
    k = min i j

我们可以通过枚举可能的浴池来检查结果，例如四个人：

Main> mapM_ print (map (distribute 4) [0 .. 50])
[0,0,0,0]
[1,0,0,0]
[1,1,0,0]
[1,2,0,0]
[1,2,1,0]
[1,2,2,0]
[1,2,3,0]
[1,2,3,1]
[1,2,3,2]
[1,2,3,3]
[1,2,3,4]
[2,2,3,4]
[3,2,3,4]
[3,3,3,4]
[3,4,3,4]
[3,5,3,4]
[3,5,4,4]
[3,5,5,4]
[3,5,6,4]
[3,5,7,4]
[3,5,7,5]
[3,5,7,6]
[3,5,7,7]
[3,5,7,8]
[3,5,7,9]
[4,5,7,9]
[5,5,7,9]
[6,5,7,9]
[6,6,7,9]
[6,7,7,9]
[6,8,7,9]
[6,9,7,9]
[6,9,8,9]
[6,9,9,9]
[6,9,10,9]
[6,9,11,9]
[6,9,12,9]
[6,9,12,10]
[6,9,12,11]
[6,9,12,12]
[6,9,12,13]
[6,9,12,14]
[6,9,12,15]
[7,9,12,15]
[8,9,12,15]
[9,9,12,15]
[10,9,12,15]
[10,10,12,15]
[10,11,12,15]
[10,12,12,15]
[10,13,12,15]