โปรแกรมหาจำนวนจุดเริ่มต้นจากจุดที่เราเริ่มเดินทางใน Python

สมมติว่ามี n เมืองที่มีตัวเลขตั้งแต่ 0 ถึง n-1 และมี n ถนนที่มีการกำหนดทิศทาง เราสามารถเดินทางจากเมือง i ไปยังเมือง (i + 1) % n [0 ถึง 1 ถึง 2 ถึง .... ไปยัง N - 1 ถึง 0] เรามีรถ ความจุของถังน้ำมันเชื้อเพลิงของรถยนต์ของเราคือหน่วยฝา มีเชื้อเพลิง[i] หน่วยของเชื้อเพลิงที่เราสามารถใช้ได้ที่จุดเริ่มต้นของเมือง i และรถใช้ต้นทุน[i] หน่วยของเชื้อเพลิงเพื่อเดินทางจากเมือง i ไปยัง (i + 1) % n เราต้องค้นหาว่ามีกี่เมืองจากจุดที่เราสตาร์ทรถ เพื่อที่เราจะได้เดินทางไปทั่วทุกเมืองและไปถึงเมืองเดียวกันที่จุดเริ่มต้น

ดังนั้น หากอินพุตเท่ากับ cap =3 เชื้อเพลิง =[3,1,2] ต้นทุน =[2,2,2] เอาต์พุตจะเป็น 2 เพราะมีวิธีแก้ปัญหาที่เป็นไปได้สองทาง

• เริ่มจากเมือง 0 เติมน้ำมัน 3 หน่วยในถัง และใช้น้ำมัน 2 หน่วยเดินทางเข้าเมือง 1 ถังเหลือ 1 หน่วย หลังจากกินน้ำมันไป 1 หน่วยที่เมือง 1 แล้ว รถมีน้ำมัน 2 หน่วย และเราสามารถเดินทางไปยังเมืองที่ 2 ได้โดยใช้น้ำมัน 2 หน่วย ตอนนี้ถังน้ำมันว่างเปล่า หลังจากเติมน้ำมัน 2 แกลลอนที่เมือง 2 แล้ว เราก็เดินทางกลับเมือง 0 โดยใช้น้ำมัน 2 แกลลอน

• เริ่มจากเมือง 2 เติมน้ำมันรถ 2 หน่วย แล้วเดินทางต่อไปยังเมือง 0 จากนั้นหลังจากเติมน้ำมัน 3 แกลลอนจากเมือง 0 เราก็เดินทางไปยังเมือง 1 และเรามีน้ำมัน 1 หน่วย จากนั้นเราสามารถเติมน้ำมันได้ 1 หน่วยที่ City 1 และตอนนี้มีน้ำมัน 2 หน่วยแล้วเดินทางเข้าเมือง 2

อย่างไรก็ตาม เราไม่สามารถเริ่มต้นจากเมือง 1 ได้ มีเชื้อเพลิงเพียง 1 หน่วย แต่การเดินทางไปยังเมือง 2 ต้องการ 2 แกลลอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดเชื้อเพลิง
• req :=อาร์เรย์ขนาด n และเติม 0
• สำหรับ k ในช่วง 0 ถึง 1 ทำ
  • สำหรับฉันในช่วง n-1 ถึง 0 ลดลง 1 ทำ
    • nexti :=(i + 1) mod n
    • req[i] :=สูงสุด 0 และ req[nexti] + cost[i] - fuel[i]
    • ถ้าขั้นต่ำของ (req[i] + fuel[i] และ cap) - cost[i]
    • คืน 0

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

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

ผลลัพธ์

2