Python程式：計算從n個球中隨機選擇k個球后，最大值和最小值之差的總和

假設我們有n個球，用陣列nums編號，陣列大小為n，nums[i]表示第i個球的編號。我們還有一個值k。每次我們從n個不同的球中選擇k個球，找到這k個球的最大值和最小值之差，並將差值儲存在一個表中。然後將這k個球放回容器中，再次選擇，直到我們選擇了所有可能的組合。最後，找到表中所有差值的總和。如果答案太大，則返回結果模10^9+7。

所以，如果輸入為n = 4，k = 3，nums = [5, 7, 9, 11]，則輸出為20，因為組合為：

  • [5,7,9]，差值 9-5 = 4
  • [5,7,11]，差值 11-5 = 6
  • [5,9,11]，差值 11-5 = 6
  • [7,9,11]，差值 11-7 = 4

所以 4+6+6+4 = 20。

為了解決這個問題，我們將遵循以下步驟：

  • m := 10^9 + 7
  • inv := 一個包含元素[0, 1]的新列表
  • 對於 i 從 2 到 n：
    • 在inv的末尾插入 (m - floor(m / i) * inv[m mod i] mod m)
  • comb_count := 1
  • res := 0
  • 對於 pick 從 k - 1 到 n - 1：
    • res := res +(nums[pick] - nums[n - 1 - pick]) * comb_count mod m
    • res := res mod m
    • comb_count := comb_count *(pick + 1) mod m * inv[pick + 2 - k] mod m
  • 返回 res

示例

讓我們來看下面的實現，以便更好地理解：

def solve(n, k, nums):
   m = 10**9 + 7

   inv = [0, 1]
   for i in range(2, n + 1):
      inv.append(m - m // i * inv[m % i] % m)

   comb_count = 1
   res = 0
   for pick in range(k - 1, n):
      res += (nums[pick] - nums[n - 1 - pick]) * comb_count % m
      res %= m
      comb_count = comb_count * (pick + 1) % m * inv[pick + 2 - k] % m

   return res

n = 4
k = 3
nums = [5, 7, 9, 11]
print(solve(n, k, nums))

輸入

4, 3, [5, 7, 9, 11]

輸出

20

更新於：2021年10月25日

瀏覽量：115

啟動您的職業生涯

透過完成課程獲得認證

開始學習
廣告