C++: Khoảng cách ngắn nhất trên trạm xe buýt vòng tròn

Bài toán: n trạm trên vòng tròn. Khoảng cách trạm i đến i+1 là D[i] (D[n-1]: n-1 → 0). Tìm khoảng cách ngắn nhất từ s đến t.

Giải pháp: Tính tổng chu vi sum. Tính khoảng cách theo chiều kim đồng hồ từ s đến t (giả sử s < t sau swap). Kết quả = min(dist, sum - dist).

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(int s, int t, vector<int> D) {
    int n = D.size();
    vector<int> pref(n + 1, 0);
    for (int i = 1; i <= n; i++)
        pref[i] = pref[i-1] + D[i-1];
    int total = pref[n];

    if (s > t) swap(s, t);
    int cw = pref[t-1] - pref[s-1]; // chiều kim đồng hồ
    return min(cw, total - cw);
}

int main() {
    vector<int> D = {2, 3, 4, 9};
    cout << solve(1, 3, D) << endl; // 5
    return 0;
}

Kết quả

5

Tổng = 18. 1→3 theo chiều kim đồng hồ: 2+3=5. Ngược chiều: 18-5=13. Min = 5.