สมมติว่าเรามีรายการ nums และค่า size, k มีการดำเนินการ: เลือกซับลิสต์ติดกันยาว size เพิ่มทุกตัว 1 สามารถทำได้ k ครั้ง หาค่าต่ำสุดที่มากที่สุดได้ใน nums
ตัวอย่าง: nums = [2, 5, 2, 2, 7], size = 3, k = 2 ผลลัพธ์ 3
ขั้นตอนการแก้ปัญหา (Binary Search + Difference Array)
- ฟังก์ชัน
possible(target):events = [0] * N,moves = s = 0- วนลูป
iจาก 0 ถึงN-1:s += events[i]delta = target - (A[i] + s)- ถ้า
delta > 0:moves += delta,s += delta- ถ้า
i + size < N:events[i + size] -= delta
- คืนค่า
moves <= K
- จากเมธอดหลัก:
N = len(A),left = 0,right = 10^10- Binary Search: while
left < right:mid = (left + right + 1) // 2- ถ้า
possible(mid):left = mid - อื่นๆ:
right = mid - 1
- คืนค่า
left
ตัวอย่างโค้ด Python
class Solution:
def solve(self, A, size, K):
N = len(A)
def possible(target):
events = [0] * N
moves = s = 0
for i in range(N):
s += events[i]
delta = target - (A[i] + s)
if delta > 0:
moves += delta
s += delta
if i + size < N:
events[i + size] -= delta
return moves <= K
left, right = 0, 10 ** 10
while left < right:
mid = (left + right + 1) // 2
if possible(mid):
left = mid
else:
right = mid - 1
return left
ob = Solution()
nums = [2, 5, 2, 2, 7]
size = 3
k = 2
print(ob.solve(nums, size, k)) # Output: 3
อินพุต / เอาต์พุต
Input: [2, 5, 2, 2, 7], 3, 2
Output: 3
