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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告