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

-1
1 4
2 6
-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\) ,因此。如果不符合条件则有四种情况

1. 左端点 \(l\) = \(min(a_l,a_{l+1},...,a_r)\) 那么最小值+1，\(l => l+1\)
2. 右端点 \(r\) = \(min(a_l,a_{l+1},...,a_r)\) 那么最小值+1，\(r => r-1\)
3. 左端点 \(l\) = \(max(a_l,a_{l+1},...,a_r)\) 那么最大值-1，\(l => l+1\)
4. 右端点 \(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);
}