Cho n (kích thước mảng), total (tổng mảng), k (chỉ số). Mảng thỏa: tổng = total, chênh lệch tuyệt đối giữa 2 phần tử liên tiếp ≤ 1. Tìm giá trị lớn nhất có thể tại chỉ số k.
Ví dụ
Input: n=5, total=15, k=3
Output: 4
Mảng khả thi: [3,2,3,4,3] (tổng=15, chênh lệch ≤1, a[3]=4).
Thuật toán: Binary Search + Công thức toán học
Giả sử giá trị tại k là x. Để tối ưu tổng (nhỏ nhất) với giá trị x tại k:
- Bên trái k: dãy giảm dần từ x về 1 (hoặc đến đầu mảng)
- Bên phải k: dãy giảm dần từ x về 1 (hoặc đến cuối mảng)
- Tổng tối thiểu = tổng dãy cộng trừ x (bị đếm 2 lần)
Công thức tổng dãy cấp số cộng: S = (first + last) * count // 2
Mã Python
def solve(n, total, k):
x = 0
while True:
# Bên trái: k+1 phần tử (0..k)
a = k + 1
s = (x + x - a + 1) * a // 2
# Bên phải: n-k phần tử (k..n-1)
a = n - k
s += (x + x - a + 1) * a // 2
# Trừ x vì bị đếm 2 lần
s -= x
if s > total:
break
x += 1
return x - 1
# Test
n, total, k = 5, 15, 3
print(solve(n, total, k)) # Output: 4Tối ưu: Binary Search
def solve(n, total, k):
def min_sum(x):
# Tổng nhỏ nhất khi a[k] = x
left_len = k + 1
right_len = n - k
left_sum = (x + max(x - left_len + 1, 1)) * left_len // 2
right_sum = (x + max(x - right_len + 1, 1)) * right_len // 2
return left_sum + right_sum - x
lo, hi = 1, total # hoặc max(total, n)
while lo <= hi:
mid = (lo + hi) // 2
if min_sum(mid) <= total:
lo = mid + 1
else:
hi = mid - 1
return hi
print(solve(5, 15, 3)) # Output: 4Phân tích độ phức tạp
- Linear search: O(x) - x = kết quả (có thể lớn)
- Binary search: O(log total) - khuyến nghị
Bài toán gốc: LeetCode 1802 - Maximum Value at a Given Index in a Bounded Array.