Rockethon 2015 C: Second Price Auction 期望 DP

题目大意

n 人竞拍，第 i 人出价均匀分布于 [l_i, r_i]。一价拍卖：最高价者得标，支付第二高价（允许并列第一）。求支付金额的期望。

解法思路：按第二高价分情况累加期望

设第二高价为 x。两种互斥情况：

1. 唯一最高价 > x：某人出价 > x，其余全 ≤ x，且至少一人 = x
2. 并列最高价 = x：至少两人出价 = x，其余 < x

对所有可能的 x（整数）累加 x * P(第二高价=x)。

概率计算

// 情况1：唯一最高价 > x
double solve1(int x) {
    double ans = 0;
    for (int i = 1; i <= n; ++i) if (r[i] > x) { // i 为最高价者
        bool ok = true, hasEq = false;
        for (int j = 1; j <= n; ++j) if (j != i) {
            if (l[j] > x) { ok = false; break; }
            if (l[j] <= x && x <= r[j]) hasEq = true;
        }
        if (!ok || !hasEq) continue;
        double pHigh = (r[i] - max(x, l[i]-1)) * 1.0 / (r[i] - l[i] + 1);
        double pAllLe = 1, pAllLt = 1;
        for (int j = 1; j <= n; ++j) if (j != i && l[j] <= x && x <= r[j]) {
            pAllLe *= (x - l[j] + 1) * 1.0 / (r[j] - l[j] + 1);
            pAllLt *= (x - l[j]) * 1.0 / (r[j] - l[j] + 1);
        }
        ans += (pAllLe - pAllLt) * pHigh;
    }
    return ans;
}

// 情况2：并列最高价 = x
double solve2(int x) {
    double ans = 0;
    for (int i = 1; i <= n; ++i) if (l[i] <= x && x <= r[i]) {
        double pEq = 1.0 / (r[i] - l[i] + 1);
        double pAllLe = 1, pAllLt = 1;
        for (int j = 1; j <= n; ++j) if (j != i && l[j] <= x && x <= r[j]) {
            pAllLe *= (x - l[j] + 1) * 1.0 / (r[j] - l[j] + 1);
            pAllLt *= (x - l[j]) * 1.0 / (r[j] - l[j] + 1);
        }
        ans += (pAllLe - pAllLt) * pEq;
    }
    return ans;
}

主流程

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &l[i], &r[i]);
    int maxR = *max_element(r+1, r+n+1);
    double ans = 0;
    for (int x = 1; x <= maxR; ++x)
        ans += (solve1(x) + solve2(x)) * x;
    printf("%.10f\n", ans);
    return 0;
}

复杂度

• 时间：O(n²·maxR) —— n≤100, maxR≤10000，约 10⁸ 操作，需常数优化
• 空间：O(n)

优化方向

• 预计算每人各区间概率
• 仅枚举端点值（概率函数分段常数）
• 前缀积加速区间乘积