ค้นหาระยะทางสูงสุดระหว่างเมืองและสถานีใด ๆ ใน Python

สมมติว่าเรามีจำนวนเมือง N จำนวน และมีจำนวนตั้งแต่ 0 ถึง N-1 และเรามีเมืองต่างๆ ที่สถานีตั้งอยู่ด้วย เราต้องหาระยะทางสูงสุดระหว่างสถานีใดสถานีหนึ่ง เมืองและสถานีที่ใกล้ที่สุด เราต้องจำไว้ว่าสามารถให้เมืองที่มีสถานีในลำดับใดก็ได้

ดังนั้นหากอินพุตเป็น N =6 และสถานี =[2,4] เอาต์พุตจะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• station_present :=รายการขนาด N และกรอกเท็จ

• สำหรับแต่ละเมืองในสถานี ทำ

  • station_present[เมือง] :=จริง

• dist :=0, maximum_dist :=สถานีต่ำสุด

• สำหรับเมืองในช่วง 0 ถึง N ให้ทำ

  • ถ้า station_present[city] เป็น True แล้ว

    • maximum_dist :=สูงสุดของ (dist + 1) / 2, maximum_dist

    • dist :=0

  • มิฉะนั้น

    • dist :=dist + 1

• คืนค่าสูงสุดของ maximum_dist, dist

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def get_max_dist(N, station):
   station_present = [False] * N
   for city in station:
      station_present[city] = True
   dist, maximum_dist = 0, min(station)
   for city in range(N):
      if station_present[city] == True:
         maximum_dist = max((dist + 1) // 2, maximum_dist)
         dist = 0
      else:
         dist += 1
   return max(maximum_dist, dist)
N = 6
station = [2, 4]
print(get_max_dist(N, station))

อินพุต

6, [2,4]

ผลลัพธ์

2