หาจุดเริ่มต้นทัวร์วงกลมครบทุกปั๊มน้ำมันใน C++

มีปั๊มน้ำมัน n แห่งจัดเรียงเป็นวงกลม แต่ละแห่งมีน้ำมันและระยะทางไปปั๊มถัดไป หาจุดเริ่มต้นที่รถบรรทุกสามารถวิ่งครบวงได้ (1 ลิตร = 1 หน่วยระยะทาง)

ตัวอย่าง: [(4,6), (6,5), (7,3), (4,5)] → เริ่มที่ Index 1 (ปั๊มที่ 2)

อัลกอริทึม (Queue-based / Two Pointers)

ใช้แนวคิด Sliding Window / Queue จำลองการเดินทาง:

1. เริ่มที่ปั๊ม 0, เก็บน้ำมันคงเหลือ (petrol - distance)
2. ขยับ end_point ไปเรื่อยๆ บวกน้ำมันคงเหลือ
3. ถ้าน้ำมันติดลบ → ขยับ start_point ทิ้งปั๊มเก่าออก จนกว่าน้ำมันจะไม่ติดลบ
4. ถ้า start_point กลับมา 0 และยังติดลบ → ไม่มีคำตอบ

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

struct Pump {
    int petrol;
    int distance;
};

int findStartIndex(Pump pumps[], int n) {
    int start = 0, end = 1;
    int curr_petrol = pumps[start].petrol - pumps[start].distance;

    while (end != start || curr_petrol < 0) {
        while (curr_petrol < 0 && start != end) {
            curr_petrol -= pumps[start].petrol - pumps[start].distance;
            start = (start + 1) % n;
            if (start == 0) return -1; // วนรอบแล้วยังติดลบ
        }
        curr_petrol += pumps[end].petrol - pumps[end].distance;
        end = (end + 1) % n;
    }
    return start;
}

int main() {
    Pump pumps[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
    int n = sizeof(pumps) / sizeof(pumps[0]);
    int start = findStartIndex(pumps, n);

    if (start == -1)
        cout << "No solution";
    else
        cout << "Index of first petrol pump: " << start;

    return 0;
}

ผลลัพธ์

Index of first petrol pump: 1

การตรวจสอบ

เริ่มที่ Index 1 (6 ลิตร, ระยะ 5):

• ปั๊ม 1: น้ำมัน 6-5=1 คงเหลือ 1
• ปั๊ม 2: +7-3=4 คงเหลือ 5
• ปั๊ม 3: +4-5=-1 คงเหลือ 4
• ปั๊ม 0: +4-6=-2 คงเหลือ 2 → ครบวงกลมสำเร็จ

วิธีอื่น: O(n) Single Pass

int findStart(vector& pumps) {
    int total = 0, curr = 0, start = 0;
    for (int i = 0; i < pumps.size(); i++) {
        int diff = pumps[i].petrol - pumps[i].distance;
        total += diff;
        curr += diff;
        if (curr < 0) {
            start = i + 1;
            curr = 0;
        }
    }
    return (total >= 0) ? start : -1;
}