Python程式：查詢任意排列的最大和

假設我們有一個數組nums，還有一個名為requests的陣列，其中requests[i] = [start_i, end_i]，這表示第i個請求要求nums[start_i] + nums[start_i+1] + ... + nums[end_i-1] + nums[end_i]的和。我們必須找到所有nums排列中所有請求的最大總和。答案可能非常大，因此返回它模10^9+7。

因此，如果輸入類似於nums = [10,20,30,40,50] requests = [[1,3],[0,1]]，則輸出將為190，因為如果我們像[30,50,40,20,10]那樣排列，我們得到：來自requests[0]：nums[1] + nums[2] + nums[3] = 50 + 40 + 20 = 110，以及來自requests[1]：nums[0] + nums[1] = 30 + 50 = 80，因此總和為110+80 = 190。

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

  • A := 一個新的列表
  • 對於requests中的每個請求(s, e)，執行：
    • 在A的末尾插入對(s, 0)
    • 在A的末尾插入對(e, 1)
  • 對列表A進行排序
  • fr := 一個空對映
  • cnt := 0
  • n := A的大小
  • i := 0
  • 當i < n時，執行：
    • r := 1
    • 當i < n - 1且A[i+1]與A[i]相同時，執行：
      • r := r + 1
      • i := i + 1
    • cnt := cnt + r
    • 如果cnt - r > 0，則
      • 在fr[cnt-r]的末尾插入(pre, p-1)
        • pre := p
    • 否則，當flag與1相同時，則
      • cnt := cnt - r
      • 在fr[cnt+r]的末尾插入(pre, p)
      • pre := p+1
    • i := i + 1
  • 反向排序列表nums
  • ks := 從fr的所有鍵的列表中建立一個新列表
  • 反向排序列表ks
  • ans := 0
  • m := 10^9 + 7
  • i := 0
  • 對於ks中的每個k，執行：
    • 對於fr[k]中的每個對(s, e)，執行：
      • d := e - s + 1
      • ans := ans + (nums[從索引i到i+d-1]的所有元素的和) * k
      • ans := ans mod m
      • i := i + d
  • 返回ans

示例

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

from collections import defaultdict
def solve(nums, requests):
   A = []
   for s, e in requests:
      A.append((s, 0))
      A.append((e, 1))
   A.sort()
   fr = defaultdict(list)
   cnt = 0

   n = len(A)
   i = 0
   while i < n:
      r = 1
      while i < n - 1 and A[i+1] == A[i]:
         r += 1
         i += 1
      p, flag = A[i]
      if flag == 0:
         cnt += r
         if cnt - r > 0:
            fr[cnt-r].append((pre, p-1))
         pre = p
      elif flag == 1:
         cnt -= r
         fr[cnt+r].append((pre, p))
         pre = p+1
      i += 1

   nums.sort(reverse=True)
   ks = list(fr.keys())
   ks.sort(reverse=True)
   ans = 0
   m = 10**9 + 7
   i = 0
   for k in ks:
      for s, e in fr[k]:
         d = e - s + 1
         ans += sum(nums[i:i+d]) * k
         ans %= m
         i += d
   return ans

nums = [10,20,30,40,50]
requests = [[1,3],[0,1]]
print(solve(nums, requests))

輸入

[10,20,30,40,50],[[1,3],[0,1]]

輸出

190

更新於：2021年10月4日

384 次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始
廣告