用 Python 编写程序使成对相邻的和变小

pythonserver side programmingprogramming更新于 2026/2/1 15:40:17

假设我们有一个非负数列表，比如 nums 和一个非负值 k。现在假设我们可以执行一个操作，在 nums 中选择一个正数并将其减 1。我们必须找到所需的最少操作数，以使列表中每对相邻值的总和 <= k。如果答案非常大，则返回结果 mod 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 := 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))