Absolute Sorting

Explicación

Ordenar el arreglo entero con una sola operación parece un poco intimidante.

La forma de simplificarlo es mirar pares adyacentes de elementos en su lugar. Si para cada par de elementos $a$ y $b$ hacemos que $|a-x| \le |b-x|$ , entonces esto implica que el arreglo entero queda ordenado.

Todavía queda un poco de análisis por casos después de notar esto:

Si $a < b$ , sabemos que $x \le \left\lfloor\frac{a+b}{2}\right\rfloor$ . Intuitivamente, esto significa que no podemos poner $x$ más allá del medio de $a$ y $b$ , porque eso haría que $x$ esté más cerca de $b$ que de $a$ .
Si $a > b$ , de forma similar tenemos $x \ge \left\lceil\frac{a+b}{2}\right\rceil$ .
En caso contrario, ambos son iguales y no importa qué valor de $x$ elijamos.

Todos estos pares limitan $x$ a un rango de números (posiblemente vacío). Mantenemos este rango a medida que recorremos el arreglo e imprimimos cualquier elemento de él al final.

Implementación

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

C++JavaPython


#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
/**
 * @return El techo de a / b.
 * A diferencia de las funciones de Java/Python, esto solo funciona para números positivos.
 */
int ceildiv(int a, int b) { return (a + (b - 1)) / b; }
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int len;
		std::cin >> len;
		vector<int> arr(len);
		for (int &i : arr) { std::cin >> i; }
 
		int at_least = INT32_MIN;
		int at_most = INT32_MAX;
		// Recorremos todos los pares adyacentes de elementos
		for (int i = 0; i < len - 1; i++) {
			// Actualizamos el rango del número que podemos usar
			if (arr[i] < arr[i + 1]) {
				at_most = std::min(at_most, (arr[i] + arr[i + 1]) / 2);
			} else if (arr[i] > arr[i + 1]) {
				at_least = std::max(at_least, ceildiv(arr[i] + arr[i + 1], 2));
			}
		}
 
		int use = std::max(at_least, 0);  // El número que usamos no puede ser negativo
		cout << (at_least <= at_most ? use : -1) << '\n';
	}
}


import java.io.*;
import java.util.*;
 
public class AbsoluteSorting {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			int len = Integer.parseInt(read.readLine());
			int[] arr = Arrays.stream(read.readLine().split(" "))
			                .mapToInt(Integer::parseInt)
			                .toArray();
			assert arr.length == len;
 
			int atLeast = Integer.MIN_VALUE;
			int atMost = Integer.MAX_VALUE;
			// Recorremos todos los pares adyacentes de elementos
			for (int i = 0; i < len - 1; i++) {
				// Actualizamos el rango del número que podemos usar
				if (arr[i] < arr[i + 1]) {
					atMost = Math.min(atMost, (arr[i] + arr[i + 1]) / 2);
				} else if (arr[i] > arr[i + 1]) {
					atLeast = Math.max(atLeast, ceildiv(arr[i] + arr[i + 1], 2));
				}
			}
 
			int use = Math.max(atLeast, 0);  // El número que usamos no puede ser negativo
			System.out.println(atLeast <= atMost ? use : -1);
		}
	}
 
	private static int ceildiv(int a, int b) { return -Math.floorDiv(a, -b); }
}


def ceildiv(a, b):
	return -(a // -b)
 
 
for _ in range(int(input())):
	len_ = int(input())
	arr = [int(i) for i in input().split()]
	assert len(arr) == len_
 
	at_least = -float("inf")
	at_most = float("inf")
	# Recorremos todos los pares adyacentes de elementos
	for i in range(len_ - 1):
		# Actualizamos el rango del número que podemos usar
		if arr[i] < arr[i + 1]:
			at_most = min(at_most, (arr[i] + arr[i + 1]) // 2)
		elif arr[i] > arr[i + 1]:
			at_least = max(at_least, ceildiv(arr[i] + arr[i + 1], 2))
 
	use = max(at_least, 0)  # El número que usamos no puede ser negativo
	print(use if at_least <= at_most else -1)