Min Max Sort

Editorial oficial (C++) 

Solución

Explicación

Si nuestro arreglo está ordenado, entonces no necesitamos realizar ninguna operación. Por lo tanto, nuestra respuesta será $0$. En caso contrario, tenemos que pensar en cómo se vería nuestra última operación para hacer que el arreglo quede ordenado como: $1, 2, 3, \dots, n$. Podemos deducir una pista importante de las operaciones mencionadas en el enunciado: nuestra última operación debe mover $1$ al frente del arreglo, y $n$ al final del arreglo para que quede ordenado.

Así que ahora sabemos cuál será nuestra última operación. Enfoquémonos en los elementos restantes: $2, 3, 4, \dots, n - 1$. Podemos aplicar el mismo análisis de arriba. O bien los números ya están ordenados, o necesitamos mover $2$ al frente y $n-1$ al final. Seguimos repitiendo esto hasta que nuestro segmento restante esté ordenado.

En cada paso, necesitamos comprobar si los números del segmento $[k, n - k + 1]$ están ordenados o no. Aquí, el segmento se refiere al subconjunto de valores (es decir, los números de $k, k + 1, k + 2, \dots, n - k + 1$), y comprobamos si aparecen en orden creciente de sus posiciones en el arreglo. Una observación clave aquí es que si un segmento $[k, n - k + 1]$ está ordenado para algún valor $k$, entonces estará ordenado también para valores mayores. Así que podemos empezar con el valor máximo de $k$ (es decir, $$\lfloor \frac{n + 1}{2} \rfloor$$) y expandirnos hacia afuera mientras el segmento siga ordenado. El punto en el que ya no podemos expandir nos da el mayor segmento medio ordenado, y el número de elementos que quedan afuera dividido por $2$ es nuestra respuesta, ya que cada operación arregla un par de elementos.

Para cada $k$, necesitamos verificar dos pares de extremos:

• ¿El número $k$ está a la izquierda de $k + 1$ en el arreglo? (es decir, $\text{index}[k] < \text{index}[k + 1]$)
• ¿El número $n - k$ está a la izquierda de $n - k + 1$ en el arreglo? (es decir, $\text{index}[n - k] < \text{index}[n - k + 1]$)

Implementación

Complejidad temporal: $\mathcal{O}(n)$

#include <iostream>
#include <vector>
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		std::cin >> n;
		std::vector<int> index(n);
		for (int i = 0; i < n; i++) {
			int x;
			std::cin >> x;
			x--;
			index[x] = i;
		}
 
		int lo = n / 2;
		int hi = n - lo;
		while (lo > 0 && index[lo - 1] < index[lo] && index[hi] > index[hi - 1]) {
			lo--;
			hi++;
		}
 
		std::cout << lo << '\n';
	}
}

import java.io.*;
import java.util.*;
 
public class MinMaxSort {
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int n = io.nextInt();
			int[] index = new int[n];
			for (int i = 0; i < n; i++) {
				int x = io.nextInt() - 1;
				index[x] = i;
			}
 
			int lo = n / 2;
			int hi = n - lo;
			while (lo > 0 && index[lo - 1] < index[lo] && index[hi] > index[hi - 1]) {
				lo--;
				hi++;
			}
 
			io.println(lo);
		}
		io.close();
	}
 
	// BeginCodeSnip{Kattio}
}

for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
 
	index = [0] * n
	for i in range(n):
		index[arr[i] - 1] = i
 
	lo = n // 2
	hi = n - lo
	while lo > 0 and index[lo - 1] < index[lo] and index[hi] > index[hi - 1]:
		lo -= 1
		hi += 1
 
	print(lo)