Tìm giá trị nhỏ nhất của độ nhảy lớn nhất để đến đảo cuối cùng đúng k nhảy trong Python

Cho mảng A chứa vị trí các đảo theo thứ tự tăng dần, và số nguyên k (1 ≤ k < N). Người đứng tại đảo 0 phải đến đảo cuối cùng đúng k nhảy. Cần tìm giá trị nhỏ nhất của độ nhảy lớn nhất trong hành trình.

Ví dụ: A = [7, 20, 41, 48], k = 2. Có 2 cách: 7→20→48 (nhảy lớn nhất 28) hoặc 7→41→48 (nhảy lớn nhất 34). Kết quả: 28.

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

• Hàm isPossible(arr, dist, k): kiểm tra có thể đến đích với độ nhảy tối đa dist và ≤ k nhảy không.
• Duyệt mảng, nhảy xa nhất có thể trong khoảng dist, đếm số nhảy cần thiết.
• Nếu số nhảy ≤ k → True.
• Hàm chính: tìm kiếm nhị phân trên khoảng [0, arr[-1]] để tìm dist nhỏ nhất thỏa mãn isPossible.

Ví dụ

def isPossible(arr, dist, k):
    n = len(arr)
    req = 0
    current = 0
    previous = 0
    for i in range(n):
        while current != n and arr[current] - arr[previous] <= dist:
            current += 1
        req += 1
        if current == n:
            break
        previous = current - 1
    if current != n:
        return False
    return req <= k

def minimum_distance(arr, k):
    n = len(arr)
    left = 0
    right = arr[-1]
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if isPossible(arr, mid, k):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

arr = [7, 20, 41, 48]
k = 2
print(minimum_distance(arr, k))

Đầu vào

[7, 20, 41, 48], 2

Đầu ra

28