Số thành phố xuất phát để đi vòng quanh trong Python

Có n thành phố 0..n-1, đường đơn chiều i → (i+1)%n. Xe có dung lượng bình xăng cap. Tại thành phố i có fuel[i] xăng, đi đến thành phố tiếp theo tốn cost[i] xăng. Tìm số thành phố xuất phát để xe đi hết vòng và quay về.

Ví dụ: cap=3, fuel=[3,1,2], cost=[2,2,2] → 2 thành phố (0 và 2).

Giải thuật

• Tính nhu cầu xăng tối thiểu tại mỗi thành phố (req[i]) bằng cách duyệt ngược 2 vòng.
• req[i] = max(0, req[next] + cost[i] - fuel[i]).
• Kiểm tra khả thi: min(req[i] + fuel[i], cap) - cost[i] >= req[next].
• Đếm số i có req[i] == 0.

Ví dụ mã Python

def solve(cap, fuel, costs):
    n = len(fuel)
    req = [0] * n
    for _ in range(2):
        for i in range(n - 1, -1, -1):
            nxt = (i + 1) % n
            req[i] = max(0, req[nxt] + costs[i] - fuel[i])
            if min(req[i] + fuel[i], cap) - costs[i] < req[nxt]:
                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))  # Output: 2

Đầu vào

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

Đầu ra

2