HDU 5035 Delivery：指數分布記憶無關性與分部積分求期望等待時間

題目大意

郵局 N 個窗口（N≤1000），每個窗口正在服務一位顧客。窗口 i 服務時間 tᵢ 滿足指數分布：p(tᵢ=t) = kᵢ e^{-kᵢ t}（kᵢ 為效率參數，0≤kᵢ≤1）。已知窗口 i 已服務 cᵢ 時間（0≤cᵢ≤1000）。馬特將去最先空閒的窗口，求他從等待到自己業務辦完的期望總時間。

核心數學：指數分布的記憶無關性

指數分布具有無記憶性：

P(T > s+t | T > s) = P(T > t)

即：已經等待了 cᵢ，剩餘服務時間分布仍為 Exp(kᵢ)，與 cᵢ 無關！
所以 cᵢ 是干擾信息，完全不影響答案。

期望推導

設所有窗口剩餘服務時間獨立分布為 Xᵢ ~ Exp(kᵢ)。馬特等待時間 = min(X₁,...,Xₙ)。
min 的指數分布仍為指數分布，參數為 Σkᵢ。故等待期望 = 1 / Σkᵢ。
隨後他選中窗口 j（概率 kⱼ / Σkᵢ），自己業務期望時間 = 1/kⱼ。
總期望 = 等待期望 + 服務期望 = 1/Σkᵢ + Σ(kⱼ/Σkᵢ)·(1/kⱼ) = 1/Σkᵢ + N/Σkᵢ = (N+1) / Σkᵢ。

分部積分驗證（原文思路）

設 x 為等待時間，y 為自己服務時間。
聯合密度：f(x,y) = (Σk) e^{-(Σk)x} · kⱼ e^{-kⱼ y}（選中窗口 j）。
期望 E[x+y] = ∫∫ (x+y) f(x,y) dx dy。
分部積分計算可得相同結果 (N+1)/Σk。

完整代碼（極簡）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cs=1; cs<=T; ++cs) {
        int N; cin >> N;
        double sumK = 0;
        for (int i=0;i> k; sumK += k; }
        for (int i=0;i> c; } // 讀掉 cᵢ，不使用
        double ans = (N + 1) / sumK;
        cout << "Case #" << cs << ": " << fixed << setprecision(6) << ans << "\n";
    }
    return 0;
}

關鍵洞察總結

1. 指數分布無記憶性：剩餘時間分布不依賴已經過時間 cᵢ
2. cᵢ 為誘餌數據：讀入即可丟棄
3. 最小值分布：min(Exp(kᵢ)) ~ Exp(Σkᵢ)
4. 選中概率正比於 kᵢ：P(選j) = kⱼ/Σk
5. 期望線性：E[等待+服務] = E[等待] + E[服務]

複雜度

• 時間：O(N) 每測試用例
• 空間：O(1)

拓展：若服務時間不滿足指數分布？

無記憶性不再成立，需用 cᵢ 計算剩餘時間條件分布，問題顯著變難。本題精妙在於識別指數分布特性，將複雜概率問題化為簡單代數計算。