หาจุดเริ่มต้นรอบแรกที่เยี่ยมปั๊มน้ำมันทุกตัวใน C++

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

• ปริมาณน้ำมันที่แต่ละปั๊มมี
• ระยะทางจากปั๊มหนึ่งไปอีกปั๊มหนึ่ง

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

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

ตัวอย่าง

#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