โปรแกรมนับจุดเริ่มต้นที่เดินทางรอบเมืองได้ใน Python

มี n เมืองเรียงวงกลม 0..n-1 มีถังน้ำมันความจุ cap เมือง i ให้น้ำมัน fuel[i] ใช้ cost[i] ไปเมืองถัดไป หาจำนวนเมืองที่เริ่มต้นได้เพื่อเดินทางรอบวงกลมครบ

ตัวอย่าง: cap=3, fuel=[3,1,2], costs=[2,2,2] → ผลลัพธ์ 2 (เมือง 0 และ 2)

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

ใช้ greedy + ตรวจสอบ feasibility แบบสองรอบ:

1. คำนวณ req[i] = น้ำมันขั้นต่ำที่ต้องมี عندถึงเมือง i เพื่อเดินทางต่อไป
2. อัปเดต req จากท้ายมาหน้า 2 รอบ
3. หากที่ใด min(req[i]+fuel[i], cap) - cost[i] < req[next] → ไม่มีจุดเริ่มต้นใดได้ คืน 0
4. นับจำนวน i ที่ req[i] == 0

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

def solve(cap, fuel, costs):
    n = len(fuel)
    req = [0] * n
    for _ in range(2):
        for i in range(n-1, -1, -1):
            next_i = (i + 1) % n
            req[i] = max(0, req[next_i] + costs[i] - fuel[i])
            if min(req[i] + fuel[i], cap) - costs[i] < req[next_i]:
                return 0
    return sum(1 for r in req if r == 0)

# ทดสอบ
cap = 3
fuel = [3, 1, 2]
costs = [2, 2, 2]
print(solve(cap, fuel, costs))  # ผลลัพธ์: 2

อินพุตตัวอย่าง

3, [3,1,2], [2,2,2]

เอาต์พุตตัวอย่าง

2