「XXI Olimpiada Informatyczna」环游世界 题解

题目分析

我们有一个环形路线，$n$ 个机场将圆周分成 $n$ 段弧，每段弧长 $l_i$。飞机满油可飞行距离为 $d$，只能在机场加油。要求从任意机场出发，绕行一圈回到起点，求最少降落次数（包括最后降落）。

关键观察

1. 环形问题转化为线性问题：将环形路线复制一份接在后面，转化为长度为 $2n$ 的线性问题
2. 可行性条件：如果存在某段弧长 $l_i > d$，则无法完成环游（输出 NIE）
3. 贪心策略：从起点出发，每次飞到能到达的最远机场

算法思路

1. 预处理检查

对于每种飞机型号 $d$，首先检查是否存在 $l_i > d$，如果存在则直接输出 NIE。

2. 环形转线性

将数组 $l$ 复制一份得到长度为 $2n$ 的数组，这样环形问题就转化为：在长度为 $2n$ 的数组中，找到长度为 $n$ 的区间，使得用贪心算法覆盖该区间所需的步数最少。

3. 双指针预处理

对于每个起点 $i$，计算从 $i$ 出发能到达的最远位置 $next[i]$：

• 使用双指针法，维护当前区间 $[i, j]$ 使得区间内弧长总和 $\leq d$
• $next[i]$ 表示从 $i$ 出发，一次加油能到达的最远机场

4. 倍增优化

由于 $n$ 最大为 $10^6$，直接对每个起点模拟贪心会超时。可以使用倍增法：

• 预处理 $f[i][k]$：从 $i$ 出发，经过 $2^k$ 次飞行能到达的最远位置
• 对于每个起点，用倍增快速计算覆盖 $n$ 个机场所需的最少步数

5. 算法步骤

def solve():
    n, s = map(int, input().split())
    l = list(map(int, input().split()))
    planes = list(map(int, input().split()))
    
    total = sum(l)
    
    # 环形转线性
    arr = l * 2
    
    for d in planes:
        # 检查可行性
        if max(l) > d:
            print("NIE")
            continue
            
        # 双指针计算next数组
        next_pos = [0] * (2*n)
        j = 0
        current_sum = 0
        for i in range(2*n):
            while j < 2*n and current_sum + arr[j] <= d:
                current_sum += arr[j]
                j += 1
            next_pos[i] = j
            current_sum -= arr[i]
        
        # 倍增预处理
        logn = (2*n).bit_length()
        f = [[0] * logn for _ in range(2*n)]
        for i in range(2*n):
            f[i][0] = next_pos[i]
        
        for k in range(1, logn):
            for i in range(2*n):
                f[i][k] = f[f[i][k-1]][k-1] if f[i][k-1] < 2*n else 2*n
        
        # 对每个起点计算最少步数
        ans = float('inf')
        for start in range(n):
            pos = start
            steps = 0
            for k in range(logn-1, -1, -1):
                if f[pos][k] < start + n:
                    pos = f[pos][k]
                    steps += (1 << k)
            steps += 1  # 最后一步
            ans = min(ans, steps)
        
        print(ans)

复杂度分析

• 可行性检查：$O(n)$
• 双指针预处理：$O(n)$
• 倍增预处理：$O(n \log n)$
• 查询每个起点：$O(n \log n)$
• 总复杂度：$O(n \log n + s \cdot n \log n)$，由于 $s \leq 100$，可以接受

算法优化

对于大规模数据，还可以进一步优化：

1. 单调队列：用单调队列维护最优起点
2. 破环成链的巧妙处理：只需要在 $[0, n)$ 范围内枚举起点

样例验证

样例输入

6 4
2 2 1 3 3 1
3 2 4 11

输出：4, NIE, 3, 2

分析：

• $d=3$：需要4次降落
• $d=2$：有弧长3>2，无法完成
• $d=4$：需要3次降落
• $d=11$：大于总周长，需要2次降落（起点和终点）

总结

本题通过环形转线性、双指针预处理和倍增优化，高效解决了飞机环游世界的最少降落次数问题。算法利用贪心性质和倍增技巧，在 $O(n \log n)$ 时间内解决问题。

最终算法标签： 贪心算法 双指针 倍增法 环形处理 预处理优化