原题链接

CF1585B Array Eversion

题目简述

现在有一个长度为 \(n\) 的序列 \(a\)，每次操作将 \(a\) 中不大于序列 \(a\) 中最后一个数的元素按照在 \(a\) 序列中的顺序放入 \(b\) 序列中，大于序列 \(a\) 中最后一个数的元素同样按照在 \(a\) 中的顺序放入 \(c\) 序列中，然后再将 \(c\) 序列拼接到 \(b\) 序列的后面，变成新的 \(a\) 序列，求至少需要几次操作才能让 \(a\) 序列不论再进行多少次操作，都不会发生变化。

解题思路

首先，这道题的正解肯定不是模拟。不难想出，让 \(a\) 序列不再变化的时候，\(a\) 序列的最后一位肯定是最大的。而每次操作后的最后一个数字一定是比当前最后一个数字大的最后一个数字，所以我们将最大值和每个数进行比较，如果大于最大值，就将次数加上 \(1\)，但是需要注意的是，因为最大值在末尾，所以最终的结果还要减去 \(1\)。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define QwQ return 0
long long t,n,a[1000010],sum,maxn;
int main()
{
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		sum=0,maxn=-1;
		cin>>n;
		for(int i=0;i<n;i++)//依次输入每个数字
			cin>>a[i];
		for(int i=n-1;i>=0;i--)//依次枚举每个数字
			if(a[i]>maxn) //如果大于最大数
				maxn=a[i],sum++; //将最大数重新赋值并将次数加上一
		cout<<sum-1<<endl;//注意，这里要减去一
	}
	QwQ;//华丽的结束
}