สมมติว่าเรามีอาร์เรย์ A ของตัวเลข ใน A หมายเลข i-th คือตำแหน่งที่มีเกาะอยู่ และให้จำนวนเต็ม k อีกตัวหนึ่ง (1 ≤ k
ดังนั้นหากอินพุตเป็น A =[7, 20, 41, 48], k =2 เอาต์พุตจะเป็น 28 เนื่องจากมีสองวิธีในการไปถึงเกาะสุดท้าย 7 ถึง 20 ถึง 48 นี่คือระยะทางสูงสุด ระหว่างเกาะสองเกาะที่ต่อเนื่องกันคือระหว่าง 48 ถึง 20 นั่นคือ 28 และ 7 ถึง 41 ถึง 48 ที่นี่ระยะห่างสูงสุดระหว่างเกาะสองเกาะที่ต่อเนื่องกันคือระหว่าง 41 ถึง 7 นั่นคือ 34 ดังนั้นขั้นต่ำ 28 และ 34 คือ 28 /P>
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
กำหนดฟังก์ชัน isPossible() นี่จะใช้เวลา arr,dist, k
n :=ขนาดของ arr
ต้องการ :=0
ปัจจุบัน :=0
ก่อนหน้า :=0
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
ในขณะที่กระแสไม่เหมือนกับ n และ (arr[current] - arr[previous]) <=dist, do
ปัจจุบัน :=ปัจจุบัน + 1
req :=req + 1
ถ้ากระแสเท่ากับ n แล้ว
ออกจากวง
ก่อนหน้า :=ปัจจุบัน - 1
ถ้ากระแสไม่เหมือนกับ n แล้ว
คืนค่าเท็จ
ถ้า req <=k แล้ว
คืนค่า True
คืนค่าเท็จ
จากวิธีหลัก ให้ทำดังนี้ −
n :=ขนาดของ arr
ซ้าย :=0
right :=องค์ประกอบสุดท้ายของ arr
ตอบ :=0
ขณะที่ซ้าย −=ขวา ทำ
กลาง :=(ซ้าย + ขวา) / 2;
ถ้า isPossible(arr, mid, k) ไม่ใช่ศูนย์ ดังนั้น
ตอบ :=กลาง
ขวา :=กลาง - 1
มิฉะนั้น
ซ้าย :=กลาง + 1
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def isPossible(arr,dist, k) :
n = len(arr)
req = 0
current = 0
previous = 0
for i in range(0, 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
if (req <= k):
return True
return False
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
