โปรแกรมสร้างผลรวมที่อยู่ติดกันเป็นคู่เล็กใน Python

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

ดังนั้น หากอินพุตเป็น nums =[4, 6, 2, 5], k =6 ผลลัพธ์จะเป็น 5 เนื่องจากเราสามารถลดรายการเป็น [3, 3, 1, 4] ซึ่งเป็นผลรวม ลดลง 5 ครั้ง ผลรวมของคู่ที่อยู่ติดกันทุกคู่คือ <=6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม =10^9 + 7
• ตอบ :=0
• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ
  • sm :=nums[i] + nums[i + 1]
  • diff :=สูงสุดของ sm - k และ 0
  • nums[i + 1] :=nums[i + 1] - ต่าง
  • ถ้า nums[i + 1] <0 แล้ว
    • nums[i + 1] :=0
  • ans :=ans + diff
• ส่งคืน 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