Chương trình tối đa hóa giá trị nhỏ nhất sau khi tăng K dãy con liên tiếp bằng Python

Cho danh sách nums, kích thước cửa sổ size và số phép toán k. Mỗi phép toán chọn một dãy con liên tiếp độ dài size và tăng tất cả phần tử lên 1. Thực hiện k phép toán, tìm giá trị nhỏ nhất lớn nhất có thể của mảng.

Ví dụ: nums = [2, 5, 2, 2, 7], size = 3, k = 2 → 3.

Quy trình giải quyết (Binary Search + Difference Array)

1. Hàm possible(target) kiểm tra có thể làm tất cả phần tử ≥ target với ≤ k phép toán không:
   • Dùng mảng events (difference array) để mô phỏng các phép tăng.
   • Duyệt mảng, giữ tổng tiền tố s của events.
   • Nếu A[i] + s < target, cần tăng thêm delta, cập nhật events[i+size] -= delta.
   • Tổng phép toán cần ≤ k.
2. Binary search trên đáp án từ 0 đến 10^10.

Ví dụ mã nguồn

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

Đầu vào

[2, 5, 2, 2, 7], 3, 2

Đầu ra

3