Min Max Sort

题目链接

题目描述：

You are given a permutation \(p\) of length \(n\) (a permutation of length \(n\) is an array of length \(n\) in which each integer from \(1\) to \(n\) occurs exactly once).

You can perform the following operation any number of times (possibly zero):

1. choose two different elements \(x\) and \(y\) and erase them from the permutation;
2. insert the minimum of \(x\) and \(y\) into the permutation in such a way that it becomes the first element;
3. insert the maximum of \(x\) and \(y\) into the permutation in such a way that it becomes the last element.

For example, if \(p=[1,5,4,2,3]\) and we want to apply the operation to the elements \(3\) and \(5\)
, then after the first step of the operation, the permutation becomes \(p=[1,4,2]\); and after we insert the elements, it becomes \(p=[3,1,4,2,5]\).

Your task is to calculate the minimum number of operations described above to sort the permutation \(p\) in ascending order (i. e. transform \(p\) so that \(p1<p2<⋯<pn\)).

输入描述：

The first line contains a single integer \(t (1≤t≤10^4)\) — the number of test cases.

The first line of the test case contains a single integer \(n (1≤n≤2⋅10^5)\) — the number of elements in the permutation.

The second line of the test case contains \(n\) distinct integers from \(1\) to \(n\) — the given permutation \(p\).

The sum of \(n\) over all test cases doesn't exceed \(2⋅10^5\).

输出描述：

For each test case, output a single integer — the minimum number of operations described above to sort the array \(p\) in ascending order.

样例：

input:

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

output:

2
0
1
3

Note:

In the first example, you can proceed as follows:

1. in the permutation \(p=[1,5,4,2,3]\), let's choose the elements \(4\) and \(2\), then, after applying the operation, the permutation becomes \(p=[2,1,5,3,4]\);
2. in the permutation \(p=[2,1,5,3,4]\), let's choose the elements \(1\) and \(5\), then, after applying operation, the permutation becomes \(p=[1,2,3,4,5]\).

AC代码：

#include <bits/stdc++.h>

using namespace std;

// 对于n个数，可以从1 ~ n, 2 ~ n - 1, 3 ~ n - 2...这样子操作
// 如果原数组中两个数的位置跟排列中的不一样就说明两个数需要操作
// 如果两个数需要操作，那么由于操作会把两个数放在最左边和最右边
// 所以在排列中这两个数左右两边的所有数也需要操作
// 所以可以从排列中间的数开始，判断原数组两个数的相对位置
// 依次往两边判断两个数是否需要操作
// 最后l和r所指的那两个数就是最先需要操作的那两个数，输出l即可
void solve()
{
	int n;
	scanf("%d", &n);

	vector<int> pos(n + 1); // 存每个数的位置

	for(int i = 1; i <= n; i ++)
	{
		int x;
		scanf("%d", &x);

		pos[x] = i; // x 的位置在 i
	}

	// 不用考虑奇偶的情况
	int l = (n + 1) / 2, r = (n + 2) / 2; 

	while(l > 0 && (l == r || (pos[l] < pos[l + 1] && pos[r - 1] < pos[r])))
	{
		l --;
		r ++;
	}

	printf("%d\n", l);
}

int main()
{
	int T;
	scanf("%d", &T);

	while(T --)
		solve();

	return 0;
}