음수가 아닌 숫자 목록이 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