Police Patrol

Explicación

Nótese que solo necesitamos intentar colocar la estación de policía en posiciones donde ya hay criminales. Entre dos posiciones vecinas de criminales, los grupos de criminales no cambian. Así, la distancia cambia de forma lineal, con la distancia mínima en un extremo.

Ahora, consideremos solo un lado de la estación. La estrategia óptima es tomar criminales en grupos de a lo sumo $m$ , empezando por los más lejanos. Para cada grupo, solo importa el criminal más lejano porque todos los criminales más cercanos se pueden recoger en el camino sin aumentar la distancia.

Así, si la estación está en $a_i$ , la distancia de ida del lado izquierdo está determinada por los criminales en los índices:

0, m, 2m, 3m, \dots

porque cada uno de estos es el criminal más lejano de un grupo.

Podemos calcular estas distancias recorriendo la lista de posiciones una vez. Cuando la posición de la estación se mueve a la derecha, cada grupo existente se vuelve más lejano en la misma cantidad. Así, si actualmente hay $\texttt{cnt}$ grupos, moverse una distancia $d$ aumenta la distancia en $\texttt{cnt} \cdot d$ . Cada vez que pasamos otro bloque de tamaño $m$ , se agrega un grupo nuevo. En otras palabras, mover la estación de $a_j$ a $a_i$ suma $\texttt{cnt} \cdot (a_i - a_j)$ a la distancia de ida.

Esto da la distancia del lado izquierdo de cada estación posible. Para obtener el lado derecho, simplemente invertimos el arreglo y ejecutamos el mismo proceso otra vez.

Para elegir $a_i$ como estación, la distancia total será la suma de la distancia izquierda y la distancia derecha. La respuesta final es el doble de la distancia mínima sobre todos los índices $i$ porque cada viaje debe volver a la estación.

Implementación

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

C++Python


#include <bits/stdc++.h>
 
std::vector<long long> side_cost(const std::vector<int> &positions, int n, int m) {
	std::vector<int> cnt(n);
	std::vector<long long> left(n);
 
	cnt[0] = 1;
	for (int i = 1; i < n; i++) {
		cnt[i] = cnt[i - 1];
 
		// extend the current cost using prev block boundary
		int pre = i - i % m;
		if (i == pre) { pre -= m; }
 
		left[i] = left[pre] + 1LL * cnt[i] * std::abs(positions[i] - positions[pre]);
 
		if (i % m == 0) {
			cnt[i] += 1;  // new block starts here
		}
	}
 
	return left;
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int n, m;
	std::cin >> n >> m;
 
	std::vector<int> positions(n);
 
	for (int &x : positions) { std::cin >> x; }
 
	m = std::min(n, m);
 
	std::vector<long long> left_cost = side_cost(positions, n, m);
	std::reverse(begin(positions), end(positions));
	std::vector<long long> right_cost = side_cost(positions, n, m);
 
	long long res = LLONG_MAX;
	for (int i = 0; i < n; i++) {
		// try every criminal position as station
		res = std::min(res, left_cost[i] + right_cost[n - i - 1]);
	}
 
	std::cout << 2LL * res << '\n';
}


def side_cost(a, n, m):
	cnt, left = [0] * n, [0] * n
	cnt[0] = 1
 
	for i in range(1, n):
		cnt[i] = cnt[i - 1]
 
		# extend the current cost using prev block boundary
		pre = i - i % m
		if i == pre:
			pre -= m
 
		left[i] = left[pre] + cnt[i] * abs(a[i] - a[pre])
		if i % m == 0:
			cnt[i] += 1  # new block starts here
 
	return left
 
 
n, m = map(int, input().split())
positions = list(map(int, input().split()))
 
m = min(n, m)
left_cost = side_cost(positions, n, m)
positions.reverse()
right_cost = side_cost(positions, n, m)
 
ans = float("inf")
for i in range(n):
	# try every criminal position as station
	ans = min(ans, left_cost[i] + right_cost[n - i - 1])
print(2 * ans)