Chương trình tạo các tổng nhỏ liền kề theo cặp bằng Python

Giả sử chúng ta có một danh sách các số không âm là num và giá trị không âm k. Bây giờ, giả sử chúng ta có thể thực hiện một phép toán trong đó chúng ta chọn một ô dương duy nhất trong số và giảm nó đi 1. Chúng ta phải tìm số phép toán tối thiểu cần thiết để mọi cặp giá trị liền kề trong danh sách có tổng <=k. Nếu câu trả lời là rất lớn, thì trả về kết quả mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như nums =[4, 6, 2, 5], k =6, thì đầu ra sẽ là 5, vì chúng ta có thể giảm danh sách thành [3, 3, 1, 4] là tổng trong số 5 sắc lệnh. Ở đây tổng của mọi cặp liền kề là <=6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m =10 ^ 9 + 7
• ans:=0
• đối với tôi trong phạm vi từ 0 đến kích thước là nums - 1, thực hiện
  • sm:=nums [i] + nums [i + 1]
  • diff:=tối đa là sm - k và 0
  • nums [i + 1]:=nums [i + 1] - diff
  • nếu nums [i + 1] <0, thì
    • nums [i + 1]:=0
  • ans:=ans + diff
• return ans mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[4, 6, 2, 5], 6

Đầu ra

5