โปรแกรมตรวจสอบว่าทุกคนสามารถนั่งได้หรือไม่ใน Python

สมมติว่าเรามีตัวเลข n แทนจำนวนคนที่กำลังหาที่นั่ง และมีรายการบิตที่ 1 แทนที่นั่งที่มีคนนั่งแล้ว ส่วน 0 แทนที่นั่งว่าง สองคนไม่สามารถนั่งติดกันได้ เราต้องตรวจสอบว่าทุกคน n คนสามารถหาที่นั่งได้หรือไม่

เช่น ถ้าอินพุตคือ n = 2 และ seats = [1, 0, 0, 0, 1, 0, 0] ผลลัพธ์จะเป็น True เพราะสามารถนั่งที่ดัชนี 2 และ 6 ได้

ขั้นตอนการแก้ปัญหา

1. แทรก 0 ไว้หน้ารายการ seats และแทรก [0, 1] ไว้ท้ายรายการ
2. กำหนด res := 0, gap := 0
3. วนลูปผ่านแต่ละค่า i ใน seats:
   • ถ้า i == 0 ให้ gap := gap + 1
   • มิฉะนั้น ถ้า gap > 0 ให้:
     • res := res + floor((gap - 1) / 2)
     • gap := 0
4. คืนค่า true ถ้า res >= n มิฉะนั้น false

def solve(n, seats):
    seats = [0] + seats + [0, 1]
    res = 0
    gap = 0
    for i in seats:
        if i == 0:
            gap += 1
        elif gap > 0:
            res += (gap - 1) // 2
            gap = 0
    return res >= n

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

2, [1, 0, 0, 0, 1, 0, 0]

True