Python程式：使相鄰元素對的和最小

假設我們有一個非負數列表nums和一個非負值k。現在假設我們可以執行一個操作，選擇nums中的一個正數並將其減1。我們必須找到所需操作的最小數量，以便列表中每對相鄰值的和<= k。如果答案非常大，則返回結果模10^9 + 7。

因此，如果輸入類似於nums = [4, 6, 2, 5]，k = 6，則輸出將為5，因為我們可以將列表遞減為[3, 3, 1, 4]，總共遞減5次。此處每對相鄰值的和<= 6。

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

  • m = 10^9 + 7
  • ans := 0
  • 對於i從0到nums的大小-1，執行：
    • sm := nums[i] + nums[i + 1]
    • diff := max(sm - k, 0)
    • nums[i + 1] := nums[i + 1] - diff
    • 如果nums[i + 1] < 0，則
      • nums[i + 1] := 0
    • ans := ans + diff
  • 返回ans mod m

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

示例

線上演示

m = 10 ** 9 + 7
class Solution:
   def solve(self, nums, k):
      ans = 0
      for i in range(0, len(nums) - 1):
         sm = nums[i] + nums[i + 1]
         diff = max(sm - k, 0)
         nums[i + 1] -= diff
         if nums[i + 1] < 0:
            nums[i + 1] = 0
         ans += diff
      return ans % m
ob = Solution()
nums = [4, 6, 2, 5]
k = 6 print(ob.solve(nums, k))

輸入

[4, 6, 2, 5], 6

輸出

5

更新於：2020年10月19日

237 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告