自动搬运

查看原文

来自洛谷，原作者为

	Dream_Stars 『 ✨少年自当扶摇上，揽星衔月勇逐光✨ 』| 支持无条件壶关，壶关请私信喵 | 你谷最蒻红名，没有之一 | 粉福 luogu.com.cn/problem/U595591

搬运于2025-08-24 23:01:48，当前版本为作者最后更新于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 养成好习惯
}