HDU 5163 Taking Bus：前綴和 + 週期性路徑模擬求最短時間

題目大意

n 個公交站 (1~n)，相鄰站距離 d_i。m 個乘客，第 i 個從 x_i 到 y_i。第 i 輛車從站 ((i-1) mod n) + 1 出發，往右行駛，到達 n 折返往左，到達 1 再折返，循環往複。車速 1 米/秒。求每位乘客最早到達目的站的時間。

關鍵觀察：路徑週期性

車輛軌跡：1 → 2 → ... → n → n-1 → ... → 1 → ...，週期長度 2*(n-1) 站段。
預計算前綴和 dist[i] = 站 1 到站 i 的距離（dist[1]=0）。
展開為長度 2n-2 的線性數組 pos[t] 表示時刻 t 車所在「虛擬站點」位置（距離原點距離）。

乘客上車時間計算

第 i 位乘客，車起點 s = (i-1)%n + 1。
情況分類：

• x ≤ y（同方向）：
  • 若 s ≤ x：車先到 x，上車時間 dist[x] - dist[s]，到達 y 再加 dist[y] - dist[x]，總時間 dist[y] - dist[s]。
  • 若 s > x：車先跑到 n 折返再回到 x，上車時間 dist[n] - dist[s] + dist[n] + dist[x]，總時間 2*dist[n] - dist[s] + dist[y]。
• x > y（反方向）：車必須先跑到 n 折返，上車時間 dist[n] - dist[s] + dist[n] - dist[x]，總時間 2*dist[n] - dist[s] - dist[y]。

C++ 代碼

#include 
using namespace std;
typedef long long LL;
const int MAXN = 200010;
LL dist[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        for (int i = 1; i < n; ++i) {
            LL d; cin >> d;
            dist[i+1] = dist[i] + d;
        }
        LL total = dist[n];
        for (int i = 1; i <= m; ++i) {
            int x, y; cin >> x >> y;
            int s = (i - 1) % n + 1;
            LL ans;
            if (x <= y) {
                if (s <= x) ans = dist[y] - dist[s];
                else ans = 2*total - dist[s] + dist[y];
            } else {
                ans = 2*total - dist[s] - dist[y];
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

複雜度

• 預處理：O(n)。
• 每查詢：O(1)。
• 總體：O(n + m) 每測試用例。

總結

HDU 5163 是「週期性運動 + 前綴和 + 分類討論」的數學建模題。核心技巧：展開折返路徑為虛擬直線距離 → 利用前綴和 O(1) 計算區間距離 → 分類起點相對位置求上車/到達時間。同類思想用於 Codeforces 週期性移動問題。