Chương trình tìm số điểm bắt đầu từ nơi chúng ta có thể bắt đầu đi du lịch bằng Python

Giả sử có n thành phố được đánh số từ 0 đến n-1 và có n đường có hướng. Chúng ta có thể đi từ thành phố i đến thành phố (i + 1)% n [0 đến 1 đến 2 đến .... đến N - 1 đến 0]. Chúng tôi có một cái xe ô tô. Dung tích của bình xăng xe của chúng tôi là đơn vị nắp. Có [i] đơn vị nhiên liệu mà chúng ta có thể sử dụng ở đầu thành phố i và chiếc xe sẽ tốn [i] đơn vị nhiên liệu để đi từ thành phố i đến (i + 1)% n. Chúng tôi phải tìm xem có bao nhiêu thành phố để có thể bắt đầu xe của mình, để chúng tôi có thể đi vòng quanh tất cả các thành phố và đến cùng một thành phố mà chúng tôi đã bắt đầu?

Vì vậy, nếu đầu vào giống như cap =3 fuel =[3,1,2] Cost =[2,2,2], thì đầu ra sẽ là 2 vì có hai giải pháp khả thi.

• chúng ta có thể bắt đầu từ thành phố 0, đổ đầy bình với 3 đơn vị nhiên liệu, và sử dụng 2 đơn vị nhiên liệu để đi đến thành phố 1. Xe tăng còn lại một đơn vị. Sau khi lấy 1 đơn vị nhiên liệu ở thành phố 1, ô tô có 2 đơn vị nhiên liệu và chúng ta có thể đi đến thành phố 2 bằng cách sử dụng 2 đơn vị nhiên liệu. Bình xăng bây giờ đã cạn. Sau khi đổ đầy 2 gallon nhiên liệu tại thành phố 2, chúng tôi sẽ quay trở lại thành phố 0 bằng cách sử dụng 2 gallon nhiên liệu.

• Chúng ta có thể bắt đầu từ thành phố 2, đổ đầy xe với 2 đơn vị nhiên liệu và đi đến thành phố 0. Sau đó, sau khi nạp 3 gallon nhiên liệu từ thành phố 0, chúng ta sẽ đi đến thành phố 1, và chúng ta có 1 đơn vị nhiên liệu. Sau đó, chúng tôi có thể tiếp nhiên liệu 1 đơn vị nhiên liệu tại Thành phố 1, và bây giờ có 2 đơn vị nhiên liệu và đi đến thành phố 2.

Tuy nhiên, chúng tôi không thể bắt đầu từ thành phố 1, chỉ có 1 đơn vị nhiên liệu hiện có, nhưng để đi đến thành phố 2 cần 2 gallon.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nhiên liệu
• req:=một mảng có kích thước n và điền bằng 0
• đối với k trong phạm vi 0 đến 1, thực hiện
  • đối với tôi trong phạm vi n-1 đến 0, giảm đi 1, thực hiện
    • nexti:=(i + 1) mod n
    • req [i]:=tối đa là 0 và req [nexti] + chi phí [i] - nhiên liệu [i]
    • nếu tối thiểu là (req [i] + fuel [i] và giới hạn) - chi phí [i]
    • trả về 0

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(cap, fuel, costs):
   n = len(fuel)
   req = [0] * n

   for k in range(2):
      for i in range(n-1, -1, -1):
         nexti = (i + 1) % n
         req[i] = max(0, req[nexti] + costs[i] - fuel[i])
         if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
            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))

Đầu vào

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

Đầu ra

2