Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

พบกับทัวร์วงกลมรอบแรกที่เข้าเยี่ยมชมปั๊มน้ำมันทั้งหมดในโปรแกรม C++


สมมติว่ามีวงกลมและมีปั๊มน้ำมันอยู่ n แห่งบนวงกลม เรามีข้อมูลสองชุดเช่น −

  • ปริมาณน้ำมันเบนซินที่ปั๊มน้ำมันทุกปั๊มมี
  • ระยะทางจากปั๊มน้ำมันหนึ่งไปยังอีกปั๊มหนึ่ง

คำนวณจุดแรกจากตำแหน่งที่รถบรรทุกจะสามารถวิ่งให้ครบวงกลมได้ สมมุติว่ารถเบนซิน 1 ลิตร รถบรรทุกสามารถวิ่งได้ 1 หน่วย สมมติว่ามีปั๊มน้ำมันสี่แห่ง และปริมาณน้ำมันและระยะทางจากปั๊มน้ำมันถัดไปเท่ากับ [(4, 6), (6, 5), (7, 3), (4, 5)], จุดแรกที่รถบรรทุกสามารถวิ่งวนได้คือปั๊มน้ำมันแห่งที่ 2 เอาต์พุตควรเริ่มต้น =1 (ดัชนีปั๊มลาดตระเวนที่สอง)

ปัญหานี้สามารถแก้ไขได้อย่างมีประสิทธิภาพโดยใช้คิว คิวจะใช้ในการจัดเก็บทัวร์ปัจจุบัน เราจะใส่ปั๊มน้ำมันแห่งแรกเข้าไปในคิว เราจะใส่ปั๊มน้ำมันจนถึง เราจะเสร็จสิ้นการเดินทาง มิฉะนั้นปริมาณน้ำมันเบนซินในปัจจุบันจะเป็นลบ หากจำนวนเงินติดลบ เราจะทำการลบปั๊มน้ำมันไปเรื่อยๆ จนกว่าจะหมด

ตัวอย่าง

#include <iostream>
using namespace std;
class pump {
   public:
   int petrol;
   int distance;
};
int findStartIndex(pump pumpQueue[], int n) {
   int start_point = 0;
   int end_point = 1;
   int curr_petrol = pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
   while (end_point != start_point || curr_petrol < 0) {
      while (curr_petrol < 0 && start_point != end_point) {
         curr_petrol -= pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
         start_point = (start_point + 1) % n;
         if (start_point == 0)
            return -1;
      }
      curr_petrol += pumpQueue[end_point].petrol - pumpQueue[end_point].distance;
      end_point = (end_point + 1) % n;
   }
   return start_point;
}
int main() {
   pump PumpArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
   int n = sizeof(PumpArray)/sizeof(PumpArray[0]);
   int start = findStartIndex(PumpArray, n);
   if(start == -1)
      cout<<"No solution";
   else
      cout<<"Index of first petrol pump : "<<start;
}

ผลลัพธ์

Index of first petrol pump : 1