题解

问题分析

题目要求计算随机引爆策略下，炸毁所有地雷所需次数的期望。核心是理解“随机选择未引爆地雷引爆”的过程，并利用概率期望的线性性质简化计算。

关键观察：

• 每次引爆操作会连锁引爆一片连续的地雷（因所有地雷在同一直线上，爆炸范围是区间）。
• 总期望可通过 线性ity of expectation 分解：设 ( X ) 为总引爆次数，( X_i ) 为“第 ( i ) 颗地雷是首次被直接引爆”的指示变量（1 表示是，0 表示否），则 ( E[X] = \sum_{i=1}^n E[X_i] )，即所有地雷“首次被直接引爆”的概率之和。

关键思路

1. 预处理爆炸范围：
   对每颗地雷 ( i )，计算其引爆后能连锁覆盖的所有地雷，形成区间 ([L_i, R_i])（因地雷按位置排序，可转化为下标区间）。

   • 排序地雷：按坐标 ( x_i ) 升序排列（输入已按位置顺序给出，可直接使用）。
   • 扩展区间：对地雷 ( i )，初始覆盖范围为 ([x_i - d_i, x_i + d_i])，通过贪心扩展找到能连锁覆盖的最大下标区间 ([L_i, R_i])（即所有坐标在该范围内的地雷）。

2. 计算概率 ( P(i) )：
   ( P(i) ) 是“地雷 ( i ) 是其所在连锁爆炸中第一个被直接引爆”的概率。

   • 对于地雷 ( i )，其所在的最小覆盖区间为 ( S_i = { j \mid L_j \leq i \leq R_j \text{ 且 } L_i \leq j \leq R_i } )（即所有能覆盖 ( i ) 且被 ( i ) 覆盖的地雷）。
   • ( P(i) = \frac{1}{|S_i|} )：因 ( S_i ) 中的地雷若有任何一个先被引爆，都会连锁引爆 ( i )，故 ( i ) 被直接引爆的概率是其在 ( S_i ) 中被首先选中的概率。

3. 求和得期望：总期望为所有 ( P(i) ) 之和。

代码实现

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    mines = []
    for _ in range(n):
        x = int(input[ptr])
        d = int(input[ptr+1])
        mines.append((x, d))
        ptr += 2
    
    # 预处理每个地雷的覆盖区间[L_i, R_i]（0-based下标）
    L = [0] * n
    R = [0] * n
    x = [m[0] for m in mines]
    d = [m[1] for m in mines]
    
    # 计算L[i]：i能覆盖的最左地雷下标
    for i in range(n):
        left = x[i] - d[i]
        # 二分找第一个x[j] >= left的j（左边界）
        low, high = 0, i
        best = i
        while low <= high:
            mid = (low + high) // 2
            if x[mid] >= left:
                best = mid
                high = mid - 1
            else:
                low = mid + 1
        L[i] = best
    
    # 计算R[i]：i能覆盖的最右地雷下标
    for i in range(n):
        right = x[i] + d[i]
        # 二分找最后一个x[j] <= right的j（右边界）
        low, high = i, n-1
        best = i
        while low <= high:
            mid = (low + high) // 2
            if x[mid] <= right:
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        R[i] = best
    
    # 扩展覆盖区间：连锁爆炸会覆盖所有能被包含的地雷
    # 迭代扩展L和R，直到不再变化
    changed = True
    while changed:
        changed = False
        for i in range(n):
            # 新的L[i]是当前L[i]到R[i]范围内最小的L[j]
            new_L = L[i]
            for j in range(L[i], R[i]+1):
                if L[j] < new_L:
                    new_L = L[j]
            # 新的R[i]是当前L[i]到R[i]范围内最大的R[j]
            new_R = R[i]
            for j in range(L[i], R[i]+1):
                if R[j] > new_R:
                    new_R = R[j]
            if new_L != L[i] or new_R != R[i]:
                L[i] = new_L
                R[i] = new_R
                changed = True
    
    # 计算每个i的S_i：所有j满足L[j] <= i <= R[j]且L[i] <= j <= R[i]
    # 即j在[L[i], R[i]]范围内，且i在[j的覆盖区间内]
    # 对于每个i，统计S_i的大小
    total = 0.0
    for i in range(n):
        cnt = 0
        # j的范围是[L[i], R[i]]
        for j in range(L[i], R[i]+1):
            if L[j] <= i <= R[j]:
                cnt += 1
        total += 1.0 / cnt
    
    # 四舍五入到小数点后四位
    print("{0:.4f}".format(round(total, 4)))

if __name__ == "__main__":
    main()

复杂度分析

1. 预处理覆盖区间：

   • 初始计算 ( L[i] ) 和 ( R[i] ) 用二分法，复杂度 ( O(n \log n) )。
   • 扩展区间的迭代过程：每次迭代扫描所有地雷，最多迭代 ( O(n) ) 次，总复杂度 ( O(n^2) )（适合 ( n \leq 4000 ) 的数据）。

2. 计算概率和：遍历每个地雷，对每个地雷扫描其覆盖区间内的所有地雷，复杂度 ( O(n^2) )。

对于大规模数据（如 ( n \leq 10^5 )），需优化扩展区间和统计 ( S_i ) 的步骤（如用线段树或单调栈压缩区间），但核心思想不变。

该方法通过线性期望分解，将复杂的期望计算转化为简单的概率求和，高效解决问题。