蓝桥杯2024年第十五届省赛真题-最强小队

解题思路:最强小队因为中间的数小于两边,所以用中间的数作为队头的话无论如何都会小于原来的最强小队。那么就可以跳过中间的的数,将队尾的数作为对头继续查找新的最强小队。在找新的最强小队的过程中,因为有相同的数,在朴素的算法下不得不遍历遍历相同的数,相同的数多的话会被卡成o(n²)。我们再次优化加入数组nex来跳过相同的数（从连续相同的数的对头跳到队尾）。这样复杂度就是o(n)了

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int nex[100005];
int dfs(int i)
{
	if(a[i]==a[i+1])
	{
		return nex[i]=dfs(i+1);
	}
	return i;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		if(!nex[i])
		{
			nex[i]=dfs(i);
		}
		
	}	
	int l=1;
	int ans=1;
	while(l!=n)
	{
		int r=l+1;
		int maxl,maxr;
		maxl=a[l];
		maxr=a[r];
		for(int i=l+1;i<=n;)
		{
			if(maxr<a[i])
			{
				r=i;
				maxr=a[i];
			}
			if(maxl<a[i])
			{
				break;
			}
			if(nex[i]==i)
			{
				i++;
			}
			else
			{
				i=nex[i];
			}
			//cout<<i<<endl;
		}
		ans=max(ans,r-l+1);		
		l=r;
	}
	printf("%d",ans);
	return 0;
}