โปรแกรมทำให้ผลรวมคู่ติดกันน้อยกว่าหรือเท่ากับ k ใน Python

สมมติว่าเรามีรายการตัวเลขไม่ติดลบ nums และค่า k ไม่ติดลบ มีการดำเนินการ: เลือกตัวเลขบวกใน nums ลดลง 1 หาจำนวนครั้งน้อยที่สุด ที่ทำให้ทุกคู่ติดกันมีผลรวม <= k ถ้าคำตอบใหญ่ คืนค่า mod 10^9+7

ตัวอย่าง: nums = [4, 6, 2, 5], k = 6 ผลลัพธ์ 5 (ลดเป็น [3, 3, 1, 4] รวม 5 ครั้ง)

ขั้นตอนการแก้ปัญหา (Greedy)

1. m = 10**9 + 7
2. ans = 0
3. วนลูป i จาก 0 ถึง len(nums)-2:
   • sm = nums[i] + nums[i+1]
   • diff = max(sm - k, 0)
   • nums[i+1] -= diff
   • ถ้า nums[i+1] < 0: nums[i+1] = 0
   • ans += diff
4. คืนค่า ans % m

ตัวอย่างโค้ด Python

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

อินพุต / เอาต์พุต

Input: [4, 6, 2, 5], 6

Output: 5