Chương trình tìm giá trị tối đa tại chỉ số cho mảng bị chặn trong Python

Mô tả bài toán

Cho n, index, maxSum. Xây dựng mảng nums kích thước n thỏa mãn:

• Tất cả phần tử > 0.
• |nums[i] - nums[i+1]| <= 1.
• Tổng các phần tử <= maxSum.
• nums[index] được tối đa hóa.

Ví dụ

Nếu n = 6, index = 3, maxSum = 8, đầu ra là 2 với mảng [1,2,2,2,1,1].

Giải thuật (Tìm kiếm nhị phân)

1. Đặt left = maxSum // n, right = maxSum + 1.
2. Trong khi left < right:
   • mid = left + (right - left) // 2.
   • Tính tổng tối thiểu bên trái (ind_l) và bên phải (ind_r) của index khi giá trị tại index là mid.
   • Nếu ind_l + ind_r <= maxSum: cập nhật ans = mid, left = mid + 1.
   • Ngược lại: right = mid.
3. Trả về ans.

Triển khai Python

def solve(n, index, maxSum):
    left, right = maxSum // n, maxSum + 1
    ans = 0
    while left < right:
        mid = left + (right - left) // 2
        ind_l = (mid - 1 + max(1, mid - index)) * min(index, mid - 1) // 2 + abs(min(0, mid - index - 1))
        ind_r = (mid + max(1, mid - (n - index - 1))) * min(n - index, mid) // 2 + abs(min(0, mid - (n - index - 1) - 1))
        if ind_l + ind_r <= maxSum:
            ans = mid
            left = mid + 1
        else:
            right = mid
    return ans

n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum))

Đầu vào

6, 3, 8

Đầu ra

2