题目分析

这是一个环形跑道上的超越问题，需要根据超越事件推断安妮卡最少完成的圈数。关键点：

• 初始时安妮卡在起点，其他人在她前面
• 超越事件可能是安妮卡超越别人，也可能是别人超越安妮卡
• 目标是计算安妮卡最少穿过终点线的次数

算法思路

核心思想

使用相对位置跟踪的方法：

1. 状态数组：a[i] 表示选手i相对于安妮卡的位置状态
2. 当前圈数：ans 记录安妮卡最少完成的圈数
3. 事件处理：根据超越事件更新状态

关键观察

• 当安妮卡超越一个正好在她前面一圈的选手时，她必须完成了一整圈
• 其他超越事件不增加必须的圈数
• 选手被超越后会落后一圈，超越别人会领先一圈

代码详解

初始化

scanf("%d%d", &n, &q);

// 初始化所有选手状态为-1（表示在安妮卡前面）
for (int i = 1; i <= n; i++)
    a[i] = -1;

int ans = 0;  // 安妮卡最少完成的圈数

初始化解释：

• a[i] = -1 表示选手i初始在安妮卡前面
• 因为比赛开始时所有其他选手都在安妮卡前方

事件处理

while (q--) {
    int x;
    scanf("%d", &x);
    
    if (x > 0) {  // 安妮卡超越了选手x
        if (a[x] == ans) {
            // 关键情况：选手x正好在安妮卡前面一圈
            a[x]++;    // 选手x又落后了一圈
            ans++;     // 安妮卡完成了一圈
        } else {
            // 一般情况：更新选手x的状态
            a[x] = ans;
        }
    } else if (a[-x] >= 0) {  // 选手-x超越了安妮卡
        // 选手-x领先了一圈
        a[-x]--;
    }
}

逻辑分析

情况1：安妮卡超越选手x (x > 0)

if (a[x] == ans) {
    a[x]++;  // 选手x落后一圈
    ans++;   // 安妮卡完成一圈
} else {
    a[x] = ans;  // 设置选手x的状态
}

解释：

• a[x] == ans 意味着：
  • 假设安妮卡完成了 ans 圈
  • 那么选手x正好在安妮卡前面一圈
• 此时安妮卡超越x，说明她又完成了一圈，所以 ans++
• 选手x现在落后一圈，所以 a[x]++
• 否则，只需要更新选手x的状态为当前圈数

情况2：选手-x超越安妮卡 (x < 0)

if (a[-x] >= 0) {
    a[-x]--;
}

解释：

• 选手-x超越了安妮卡，意味着他领先了一圈
• 所以他的相对位置减少1（更领先）
• a[-x] >= 0 检查选手状态是否有效（已被初始化）

输出结果

printf("%d\n", ans);

算法原理

状态表示的意义

a[i] 表示：如果安妮卡完成了 ans 圈，那么选手i相对于安妮卡的位置

具体含义：

• a[i] < ans：选手i在安妮卡前面
• a[i] == ans：选手i正好在安妮卡前面一圈
• a[i] > ans：选手i在安妮卡后面

为什么这样能计算最少圈数？

关键引理：安妮卡完成一整圈的必要条件是超越一个正好在她前面一圈的选手。

证明：

1. 初始时所有人在安妮卡前面
2. 要完成第一圈，必须超越所有最初在前面的选手至少一次
3. 但不需要每次都增加圈数，只需要在必须的时候计数

算法只在这种情况下增加 ans：

• 安妮卡超越选手x
• 且 a[x] == ans（选手x正好在安妮卡前面一圈）

样例分析

样例1

输入：

4
5
-2  // 2号超越安妮卡
2   // 安妮卡超越2号
1   // 安妮卡超越1号
-3  // 3号超越安妮卡
2   // 安妮卡超越2号

执行过程：

1. -2：a[2]-- → a[2] = -2
2. 2：a[2](-2) ≠ ans(0) → a[2] = 0
3. 1：a[1](-1) ≠ ans(0) → a[1] = 0
4. -3：a[3]-- → a[3] = -2
5. 2：a[2](0) == ans(0) → a[2]++=1, ans++=1

输出：1

样例2

输入：

2
4
1 1 1 1

执行过程：

1. 第一次 1：a[1](-1) ≠ ans(0) → a[1] = 0
2. 第二次 1：a[1](0) == ans(0) → a[1]++=1, ans++=1
3. 第三次 1：a[1](1) == ans(1) → a[1]++=2, ans++=2
4. 第四次 1：a[1](2) == ans(2) → a[1]++=3, ans++=3

输出：3

复杂度分析

时间复杂度

• 初始化：$O(n)$
• 事件处理：$O(Q)$
• 总复杂度：$O(n + Q)$

空间复杂度

• 状态数组：$O(n)$
• 其他变量：$O(1)$

关键技巧

1. 相对位置表示：用整数差表示圈数关系
2. 最小化计数：只在必要时增加圈数
3. 状态初始化：-1表示初始在前方
4. 边界处理：检查状态有效性