Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 쌍으로 인접한 합을 작게 만드는 프로그램

<시간/>

음수가 아닌 숫자 목록이 nums이고 음수가 아닌 값 k가 있다고 가정합니다. 이제 숫자에서 단일 양수를 선택하고 1로 줄이는 연산을 수행할 수 있다고 가정합니다. 목록에 있는 모든 인접 값의 합이 <=k가 되도록 필요한 최소 연산 수를 찾아야 합니다. 답이 매우 크면 결과 모드 10^9 + 7을 반환합니다.

따라서 입력이 nums =[4, 6, 2, 5], k =6과 같으면 목록을 [3, 3, 1, 4]로 감소시킬 수 있으므로 출력은 5가 됩니다. 5 감소. 여기서 모든 인접한 쌍의 합은 <=6입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • m =10^9 + 7
  • ans :=0
  • 0부터 숫자 - 1까지의 범위에 있는 i에 대해
    • sm :=숫자[i] + 숫자[i + 1]
    • diff :=sm - k 및 0의 최대값
    • 숫자[i + 1] :=숫자[i + 1] - 차이
    • 숫자[i + 1] <0이면
      • 숫자[i + 1] :=0
    • ans :=as + 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