โปรแกรมหาระยะห่างสูงสุดระหว่างที่นั่งว่างและที่นั่งที่มีคนใน Python

การหาระยะห่างสูงสุดจากที่นั่งว่างไปที่นั่งที่มีคนใกล้สุด

กำหนดรายการ seats (0=ว่าง, 1=มีคน) มีที่นั่งว่างอย่างน้อย 1 และมีคนอย่างน้อย 1 หาระยะห่างสูงสุดจากที่นั่งว่างไปที่นั่งที่มีคนใกล้ที่สุด

อัลกอริทึม

1. res = 0, last = -1 (index ที่นั่งที่มีคนล่าสุด)
2. วนลูป i = 0 ถึง n-1
3. ถ้า seats[i] == 1:
   • ถ้า last == -1 (คนแรก) → ระยะห่าง = i (จาก đầu)
   • ถ้า last != -1 → ระยะห่าง = (i - last) // 2 (กึ่งกลางระหว่างสองคนนั่ง)
   • อัปเดต res = max(res, ระยะห่าง)
   • last = i
4. หลังลูป: พิจารณาท้ายสุด → ระยะห่าง = n - last - 1
5. คืนค่า max(res, ท้ายสุด)

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

def solve(seats):
    res, last, n = 0, -1, len(seats)
    for i in range(n):
        if seats[i]:
            res = max(res, i if last < 0 else (i - last) // 2)
            last = i
    return max(res, n - last - 1)

seats = [1, 0, 1, 0, 0, 0, 1]
print(solve(seats))

ผลลัพธ์

2

คำอธิบาย

seats = [1, 0, 1, 0, 0, 0, 1]

• คนที่ 0: ระยะจากหน้า = 0
• คนที่ 2: ระยะกึ่งกลาง (2-0)//2 = 1
• คนที่ 6: ระยะกึ่งกลาง (6-2)//2 = 2, ท้ายสุด = 7-6-1 = 0
• สูงสุด = 2 (ที่นั่ง index 4 ระยะ 2 จากคน index 2 และ 6)