CF1793C Dora and Search Difficulty：1200

题意翻译

题目描述

给定一个长度为 $n$ 的排列 $a$ ，问是否存在正整数 $l,r$ 使得 $a_l,a_r$ 均不为 $a_{l...r}$ 中的最大值或最小值。

输入输出格式

第一行一个正整数 $t$ ，表示数据组数。接下来对于每组数据输入包括两行，第一行一个正整数 $n$ ，第二行 $n$ 个正整数代表排列 $a$ 。
对于每组数据，若存在符合要求的 $l,r$ ，输出任意一组。若不存在则输出 $-1$ 。

数据范围

$1\leqslant t \leqslant 10\ 000\ ,\ 1\leqslant \Sigma n \leqslant 200\ 000\ ,\ $ $a$ 是一个排列。

输入输出样例

输入样例 #1

4
3
1 2 3
4
2 1 4 3
7
1 3 2 4 6 5 7
6
2 3 6 5 4 1

输出样例 #1

说明

对于第一组样例，$(l,r)={(1,2),(1,3),(2,3)}$时都不能满足 $min(a_l,a_{l+1}...a_r)或max(a_l,a_{l+1}...a_r)≠a_l或a_r$

对于第二组样例，当 $l=1,r=4$ 时, $min(2,1,4,3)=1,max(2,1,4,3)=4,minpos=2,maxpos=3$ 符合题意

题解

本题思路为双指针，左指针 $l$ 和右指针 $r$ 分别初始为$1$和$n$ ,因此。如果不符合条件则有四种情况

左端点 $l$ = $min(a_l,a_{l+1},...,a_r)$ 那么最小值+1，$l => l+1$
右端点 $r$ = $min(a_l,a_{l+1},...,a_r)$ 那么最小值+1，$r => r-1$
左端点 $l$ = $max(a_l,a_{l+1},...,a_r)$ 那么最大值-1，$l => l+1$
右端点 $r$ = $max(a_l,a_{l+1},...,a_r)$ 那么最大值-1，$

每次都需要往中间并拢，因为你无论如何都不能通过以这个节点为l或r,找到一组满足要求的l和r

参考代码

void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",a+i); 
	int ansl=1,ansr=n,minx=1,maxx=n;
	//双指针,从左右端点开始向中间靠拢，不满足条件移动指针，并修改min(al-ar) or max(al-ar) 
	while(ansl<=ansr)
	{
		if(a[ansl]==minx)ansl++,minx++;
		else if(a[ansl]==maxx)ansl++,maxx--;
		else if(a[ansr]==minx)ansr--,minx++;
		else if(a[ansr]==maxx)ansr--,maxx--;
		else break;
	}
	if(ansl>ansr)puts("-1");
	else printf("%d %d\n",ansl,ansr);
}