题解：P10844 [EGOI2024] Infinite Race / 无限赛跑

Dream_Stars · 2024-08-23 08:34:16 · 题解

题目大意：

有 N 位参赛者去跑马拉松，Anika 是第 0 位参赛者，最开始在队伍末尾，其中发生了 Q 次超越或者被超越 Anika 的事件，求出至少穿过终点线的次数。

算法分析：

考虑模拟。\ 这道题对于超过终点线的判定如下：\ 若原来在 x 后的 y 超过了 x 一次，那么无法判定 y 过了终点线，因为可能在同一圈里，只不过前后关系变了，只有在 y 连续超过两次 x 时，那么就是套圈的现象，要发生就必然需要经过一次终点线。\ 知道了这点，我们就可以用模拟的算法求解。

我们可以使用一个 a 数组来保存超过或者和被超过次数，如果有两次超过，那么就算作超过一次终点线，那个位置的值清空。

代码展示：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 * 2 + 10;
long long ans,n,t,x,a[N];
int main()
{
  scanf("%lld%lld",&n,&t);
  ans = 1;//ans最开始赋1，便利统计
  for(int i = 1 ; i <= t ; i++){
    scanf("%lld",&x);
//分成两种情况讨论
    if(x <= 0)
      a[abs(x)] = 0;//被超过，那么那个位置的人就无法被连续超过两次，故清零
    else{
      if(a[x] == ans) ans++;
      a[x] = ans;//判断
    }
  }
  cout << ans - 1 ;
  return 0;//return 养成好习惯
}