หาค่าสูงสุดของระยะทางกระโดดขั้นต่ำเพื่อไปถึงเกาะสุดท้ายใน k ครั้งใน Python

สมมติว่าเรามีอาร์เรย์ A ที่เก็บตำแหน่งของเกาะ (เรียงจากน้อยไปมาก) และจำนวนเต็ม k (1 ≤ k < N) คนอยู่ที่เกาะที่ 0 ต้องไปถึงเกาะสุดท้ายโดยกระโดดพอดี k ครั้ง หาค่าที่น้อยที่สุดของระยะทางกระโดดสูงสุดในเส้นทาง

เช่น A = [7, 20, 41, 48], k = 2 ผลลัพธ์คือ 28 เส้นทาง 7→20→48 ระยะทางสูงสุด 28 (48-20) เส้นทาง 7→41→48 ระยะทางสูงสุด 34 เลือกค่าน้อยกว่าคือ 28

ขั้นตอนการแก้ปัญหา (Binary Search + Greedy)

1. สร้างฟังก์ชัน isPossible(arr, dist, k) ตรวจสอบว่าสามารถไปถึงท้ายได้ด้วยระยะทางสูงสุด dist และไม่เกิน k ครั้ง
2. ใช้ two-pointer นับจำนวนครั้งที่ต้องกระโดด
3. ในฟังก์ชันหลัก ใช้ Binary Search บนคำตอบ:
   • left = 0, right = arr[-1]
   • ตรวจสอบ mid ด้วย isPossible ปรับช่วงค้นหา

ตัวอย่างโค้ด Python

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))

อินพุต

[7, 20, 41, 48], 2

เอาต์พุต

28