Chương trình làm cho tổng các cặp liền kề nhỏ hơn hoặc bằng k bằng Python

Cho danh sách nums số không âm và giá trị k. Mỗi phép toán chọn một số dương trong nums và giảm nó đi 1. Tìm số phép toán tối thiểu sao cho tổng mọi cặp liền kề ≤ k. Kết quả modulo 10^9+7.

Ví dụ: nums = [4, 6, 2, 5], k = 6 → 5 (giảm thành [3, 3, 1, 4]).

Quy trình giải quyết (Greedy)

1. Khởi tạo ans = 0.
2. Duyệt i từ 0 đến len(nums)-2:
   • Tính sm = nums[i] + nums[i+1].
   • diff = max(sm - k, 0).
   • Giảm nums[i+1] đi diff (nếu âm thì đặt 0).
   • ans += diff.
3. Trả về ans % (10^9+7).

Ví dụ mã nguồn

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))  # Output: 5

Đầu vào

[4, 6, 2, 5], 6

Đầu ra

5