จำนวนจุดเติมน้ำมันขั้นต่ำใน C++

สมมติว่ามีรถที่เดินทางจากตำแหน่งเริ่มต้นไปยังปลายทางซึ่งอยู่ห่างจากตำแหน่งเริ่มต้นไปทางทิศตะวันออก t ไมล์

ระหว่างทางมีปั๊มน้ำมันหลายแห่ง ดังนั้น แต่ละสถานี[i] แทนปั๊มน้ำมันที่สถานี[i][0] ไมล์ทางตะวันออกของตำแหน่งเริ่มต้น และสถานีนั้นมีสถานี[i][1] น้ำมัน

หากรถสตาร์ทด้วยขนาดถังแก๊สที่ไม่มีที่สิ้นสุดซึ่งในตอนแรกมีการสตาร์ทน้ำมันเชื้อเพลิงอยู่เป็นลิตร ใช้น้ำมัน 1 ลิตรต่อ 1 ไมล์ที่ขับ

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

ดังนั้นหากอินพุตเป็นเหมือน Target =100 startFuel =20 สถานี =[10,40],[20,30],[30,20],[60,40] เอาต์พุตจะเป็น 3 ดังนั้นในขั้นต้น มีน้ำมัน 10 ลิตร พอถึงสถานีแรกจะถ่ายน้ำมัน 40 ลิตร ปัจจุบันมีน้ำมัน (0 + 40) =40 ลิตร พอถึงสถานีที่ 3 ตอนนี้ถ่ายน้ำมัน 20 ลิตร ดังนั้นกระแสไฟ ปริมาณคือ (20+20) =40 แล้วถึงสถานีสุดท้าย กินน้ำมัน 40 ลิตร ดังนั้นปริมาณปัจจุบัน (10 + 40) =50 ถึงตอนนี้เราวิ่งไปแล้ว 60 ไมล์ เราต้องไปอีก 40 ไมล์กว่าจะถึง ปลายทางมีน้ำมันเพียงพอที่จะไปถึงเป้าหมาย

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

• สกุลเงิน :=0

• เรียงลำดับอาร์เรย์ st

• กำหนดลำดับความสำคัญ pq

• ผม :=0, cnt :=0

• curr :=curr + เชื้อเพลิง

• ในขณะที่เคอร์เรน <เป้าหมาย ทำ -

  • (เพิ่มขึ้นอีก 1)

  • ในขณะที่ (i <ขนาดของ st และ st[i, 0] <=curr) ทำ −

    • แทรก st[i, 1] ลงใน pq

    • (เพิ่ม i ขึ้น 1)

  • ถ้า pq ว่างเปล่า −

    • ออกจากวง

  • curr :=curr + องค์ประกอบด้านบนของ pq

  • ลบองค์ประกอบออกจาก pq

• return (ถ้า curr>=target แล้ว cnt มิฉะนั้น -1)

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

ตัวอย่าง

#include ใช้เนมสเปซ std;class Solution { สาธารณะ:int minRefuelStops (int เป้าหมาย เชื้อเพลิง int เวกเตอร์ > &st) { int curr =0; เรียงลำดับ(st.begin(), st.end()); Priority_queue pq; int ผม =0; int cnt =0; สกุลเงิน +=เชื้อเพลิง; ในขณะที่ (curr <เป้าหมาย) { cnt++; ในขณะที่ (i =เป้าหมาย ? cnt :-1; }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{10,40},{20,30},{30,20},{60,40}}; cout <<(ob.minRefuelStops(100, 10, v));}

อินพุต

ผลลัพธ์

3