Skip to Content
CTRL K

Max Median

Editorial oficial 

Explicación

Podemos hacer búsqueda binaria sobre la mayor mediana posible de alcanzar.

Para comprobar si la mediana xx es alcanzable en un intervalo, necesitamos contar el número de elementos que son ≥x\ge x y el número de elementos que son <x< x.

Si el número de elementos ≥x\ge x es mayor que el número de elementos <x< x, podemos decir que esta mediana es alcanzable. Observemos que debe haber estrictamente más elementos mayores o iguales que xx que menores que xx por cómo el problema define la mediana para subarreglos de tamaño par.

Sea f(i)f(i) el número de elementos del prefijo que son ≥x\ge x menos el número de elementos del prefijo que son <x< x.

Podemos demostrar que si f(i)−f(j)>0f(i) - f(j) > 0 e i>=j+ki >= j + k, es posible tener una mediana de xx. Esto se debe a que en el rango de ii a jj habrá más elementos mayores o iguales que xx que menores que xx, lo que significa que la mediana también será mayor o igual que xx.

A partir de aquí podemos hacer una búsqueda lineal de la diferencia máxima, llevando el registro del elemento mínimo del prefijo de 00 a f[i−k]f[i - k], lo que asegura que el tamaño sea siempre al menos kk. Si es mayor que 00, entonces esta mediana es posible de alcanzar.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int &i : a) { cin >> i; }
 
	// Búsqueda binaria de la mediana máxima
	int lo = 1;
	int hi = n;
	while (lo < hi) {
		int median = (lo + hi + 1) / 2;
		// Igual que la f descrita en la editorial
		vector<int> f(n);
		for (int i = 0; i < n; i++) {
			/*
			 * Si a[i] es mayor o igual que la mediana,
			 * aporta 1 a f(i). En caso contrario, si es menor que la mediana,
			 * aporta -1 a f(i)
			 */
			f[i] = a[i] >= median ? 1 : -1;
			if (i) { f[i] += f[i - 1]; }
		}
 
		// Lleva el registro del valor mínimo de f(x) en el prefijo
		int mn = 0;
		int diff = 0;
		// Iterar sobre el puntero final de un subarreglo.
		for (int i = k - 1; i < n; i++) {
			// Actualizar el elemento mínimo del prefijo.
			mn = min(mn, f[i - k]);
			// Actualizar la diferencia máxima posible.
			diff = max(diff, f[i] - mn);
		}
 
		// Actualizar las cotas de la búsqueda binaria.
		if (diff > 0) {
			lo = median;
		} else {
			hi = median - 1;
		}
	}
 
	cout << lo << endl;
}
import java.io.*;
import java.util.*;
 
public class MaxMedian {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
 
		st = new StringTokenizer(br.readLine());
		int[] a = new int[n];
		for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); }
 
		// Búsqueda binaria de la mediana máxima
		int lo = 1;
		int hi = n;
		while (lo < hi) {
			int median = (lo + hi + 1) / 2;
			// Igual que la f descrita en la editorial
			int[] f = new int[n];
			for (int i = 0; i < n; i++) {
				/*
				 * Si a[i] es mayor o igual que la mediana,
				 * aporta 1 a f(i). En caso contrario, si es menor que la mediana,
				 * aporta -1 a f(i)
				 */
				f[i] = a[i] >= median ? 1 : -1;
				if (i > 0) { f[i] += f[i - 1]; }
			}
 
			// Lleva el registro del valor mínimo de f(x) en el prefijo
			int mn = 0;
			int diff = 0;
			// Iterar sobre el puntero final de un subarreglo.
			for (int i = k - 1; i < n; i++) {
				// Actualizar el elemento mínimo del prefijo.
				if (i - k >= 0) { mn = Math.min(mn, f[i - k]); }
				// Actualizar la diferencia máxima posible.
				diff = Math.max(diff, f[i] - mn);
			}
 
			// Actualizar las cotas de la búsqueda binaria.
			if (diff > 0) {
				lo = median;
			} else {
				hi = median - 1;
			}
		}
 
		pw.println(lo);
		pw.close();
	}
}
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
 
# Búsqueda binaria sobre la mediana máxima
lo = 1
hi = n
while lo < hi:
	median = (lo + hi + 1) // 2
	# Igual que la f descrita en la editorial
	f = []
	for i in range(n):
		# Si a[i] es mayor o igual que la mediana, aporta 1 a f(i)
		# En caso contrario, si es menor que la mediana, aporta -1 a f(i)
		f.append(1 if a[i] >= median else -1)
		if i > 0:
			f[i] += f[i - 1]
 
	# Lleva el registro del valor mínimo de f(x) en el prefijo
	mn = 0
	diff = 0
	# Iterar sobre el puntero final de un subarreglo.
	for i in range(k - 1, n):
		# Actualizar el elemento mínimo del prefijo.
		if i - k >= 0:
			mn = min(mn, f[i - k])
		# Actualizar la diferencia máxima posible.
		diff = max(diff, f[i] - mn)
 
	# Actualizar las cotas de la búsqueda binaria.
	if diff > 0:
		lo = median
	else:
		hi = median - 1
 
print(lo)
Fundamentos