Cho số nguyên n và danh sách ràng buộc restrictions với restrictions[i] = (id_i, max_height_i). Cần xây n tòa nhà liền kề (1..n) thỏa: (1) chiều cao ≥ 0, (2) tòa 1 cao độ 0, (3) chênh lệch cao độ giữa 2 tòa liền kề ≤ 1. Tìm chiều cao lớn nhất có thể của tòa cao nhất.
Ví dụ: n = 5, restrictions = [[2,1],[4,3]] → output = 4.
Giải thuật (Two-pass + Peak calculation)
- Sắp xếp restrictions theo id.
- Pass 1 (trái→phải): lan truyền ràng buộc max_height[i] = min(max_height[i], prev_height + dist).
- Pass 2 (phải→trái): lan truyền ngược.
- Duyệt lại restrictions: giữa 2 ràng buộc liên tiếp, đỉnh cao nhất có thể = (f + ff + dist) // 2.
- Cũng xét đỉnh sau ràng buộc cuối: f + (n - last_id).
Code Python
def solve(n, restrictions):
if not restrictions:
return n - 1
resi = sorted(restrictions, key=lambda x: x[0])
k, idx = 0, 1
for re in resi:
re[1] = min(re[1], k + re[0] - idx)
k, idx = re[1], re[0]
k, idx = resi[-1][1], resi[-1][0]
resi.reverse()
for re in resi[1:]:
re[1] = min(re[1], k - re[0] + idx)
k, idx = re[1], re[0]
resi.reverse()
f, idx, res = 0, 1, 0
for re in resi:
ff = min(f + re[0] - idx, re[1])
res = max(res, (re[0] - idx + f + ff) // 2)
idx, f = re[0], ff
return max(f + n - idx, res)
n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions)) # 4
Đầu vào / Đầu ra
Input: 5, [[2,1],[4,3]]
Output: 4