Sabotage

Explicación

Podemos hacer búsqueda binaria sobre valores reales para hallar el promedio mínimo $X$ que podemos lograr.

Ahora, si hallamos el arreglo de sumas de prefijos $\texttt{pref}$ del arreglo de producción de leche $M$ , consideremos la condición que necesitamos para lograr un promedio $\le X$ al quitar el subarreglo $(i, j]$ :

\frac{S-\left(\texttt{pref}[j]-\texttt{pref}[i]\right)}{N-\left(j-i\right)}\le X,

donde $S$ es la suma actual del arreglo. Tras multiplicar ambos lados por el denominador y aislar todos los términos que involucran a $i$ , obtenemos:

\texttt{pref}[i]-X\cdot i\le X\cdot\left(N-j\right)-S+\texttt{pref}[j].

Para un $j$ fijo, deberíamos intentar minimizar la expresión del lado izquierdo. Así que podemos iterar $j$ de $2$ a $N - 1$ y mantener un mínimo corriente del lado izquierdo de la desigualdad. Si la condición se cumple, podemos lograr un promedio $\le X$ .

Como alternativa, se puede restar el promedio $X$ que se está verificando de cada valor de $M$ , lo que da un arreglo donde el promedio de un conjunto en $M$ es menor o igual que $X$ si y solo si la suma del conjunto correspondiente en el arreglo modificado es menor o igual que $0$ . Esto significa que se desea la suma máxima de subarreglo del arreglo modificado excepto el primer y el último elemento para minimizar el promedio de la suma modificada de los elementos restantes, obtenida con un método voraz.

Para ver que esto es equivalente al enfoque principal, notemos que la suma de $[l, r]$ en el arreglo modificado es la suma en el arreglo original menos $X\cdot (r-l+1)$ . Usar esto para reescribir el arreglo de sumas de prefijos y así la última ecuación de la solución principal da el mismo objetivo de optimización.

Implementación

Complejidad temporal: $\mathcal{O}(N\log\left(\frac{1}{\varepsilon}\right))$ , donde $\varepsilon$ es el margen de error fijo.

C++Python


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("sabotage.in", "r", stdin);
	freopen("sabotage.out", "w", stdout);
 
	int n;
	cin >> n;
	vector<int> m(n);
	for (int i = 0; i < n; i++) cin >> m[i];
 
	// Sumas de prefijos del arreglo de producción de leche m
	vector<long long> pref_sum(n + 1);
	for (int i = 0; i < n; i++) { pref_sum[i + 1] = pref_sum[i] + m[i]; }
 
	long long arr_sum = pref_sum[n];
 
	// Función de verificación para ver si se puede lograr el promedio x
	auto check = [&](double x) {
		double left_side = pref_sum[1] - x;
		for (int j = 2; j <= n - 1; j++) {
			double right_side = x * (n - j) - arr_sum + pref_sum[j];
			if (left_side <= right_side) { return true; }
			left_side = min(left_side, pref_sum[j] - x * j);
		}
		return false;
	};
 
	double l = 1, r = 10000;
 
	while (r - l > 1e-4) {
		double mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
 
	cout << fixed << setprecision(3) << l << "\n";
}


with open("sabotage.in", "r") as read:
	n = int(read.readline())
	m = [int(read.readline()) for i in range(n)]
 
pref_sum = [0]
for i in range(n):
	pref_sum.append(pref_sum[-1] + m[i])
arr_sum = sum(m)
 
 
def check(x):
	left_side = pref_sum[1] - x
	for j in range(2, n):
		right_side = x * (n - j) - arr_sum + pref_sum[j]
		if left_side <= right_side:
			return True
		left_side = min(left_side, pref_sum[j] - x * j)
	return False
 
 
l, r = 1, 10000
while r - l > 1e-4:
	mid = (l + r) / 2
	if check(mid):
		r = mid
	else:
		l = mid
 
print(f"{l:.3f}", file=open("sabotage.out", "w"))