Skip to Content
CTRL K

Permutator

Análisis oficial (C++) 

Explicación

Simplificación

Primero, dejemos de lado todo lo raro de los subarreglos y miremos la siguiente simplificación:

Dados dos arreglos aa y bb, permutar bb para minimizar ∑i=0n−1ai⋅bi\sum_{i=0}^{n-1} a_i \cdot b_i.

Esta versión más simple se resuelve con un enfoque voraz (greedy). Emparejamos el elemento más grande de aa con el más pequeño de bb, el segundo más grande de aa con el segundo más pequeño de bb, y así sucesivamente hasta haber emparejado todos.

La intuición es que queremos minimizar el impacto que los elementos más grandes de aa tendrán en la suma, así que los emparejamos con los más pequeños de bb.

El problema original

Lamentablemente, el problema original no es tan simple.

Sin embargo, nótese que podemos precomputar el número de ocurrencias en las que un índice particular kk aparecerá entre todas las sumas.

Con esto, si sabemos que a2⋅b2a_2 \cdot b_2 aparecerá exactamente 55 veces en la suma, entonces podemos multiplicar de antemano a2a_2 por 55 antes de hacer el emparejamiento de nuestra simplificación.

Si usamos indexación desde cero, cada índice kk se incluye en (k+1)⋅(n−k)(k + 1) \cdot (n - k) posiciones. Esto se debe a que hay k+1k+1 posiciones de inicio para subarreglos a la izquierda y n−kn-k posiciones de fin a la derecha.

Luego, podemos multiplicar cada elemento de aa por su número de ocurrencias para reducir esto a nuestro problema más simple.

Implementación

Complejidad temporal: O(nlog⁡n)\mathcal{O}(n \log n)

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int len;
	std::cin >> len;
	vector<int> a(len);
	for (int &i : a) { std::cin >> i; }
	vector<int> b(len);
	for (int &i : b) { std::cin >> i; }
 
	vector<long long> subarr_num(len);
	for (int i = 0; i < len; i++) { subarr_num[i] = (long long)(i + 1) * (len - i); }
 
	vector<long long> actual_a(len);
	for (int i = 0; i < len; i++) { actual_a[i] = subarr_num[i] * a[i]; }
 
	std::sort(actual_a.begin(), actual_a.end());
	std::sort(b.begin(), b.end(), std::greater<int>());
 
	long long total = 0;
	for (int i = 0; i < len; i++) { total += actual_a[i] * b[i]; }
	cout << total << endl;
}
import java.io.*;
import java.util.*;
 
public class Permutator {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int len = Integer.parseInt(read.readLine());
		int[] a = Arrays.stream(read.readLine().split(" "))
		              .mapToInt(Integer::parseInt)
		              .toArray();
		int[] b = Arrays.stream(read.readLine().split(" "))
		              .mapToInt(Integer::parseInt)
		              .toArray();
 
		long[] subarrNum = new long[len];
		for (int i = 0; i < len; i++) { subarrNum[i] = (long)(i + 1) * (len - i); }
 
		long[] actualA = new long[len];
		for (int i = 0; i < len; i++) { actualA[i] = subarrNum[i] * a[i]; }
 
		Arrays.sort(actualA);
		Arrays.sort(b);
 
		long total = 0;
		for (int i = 0; i < len; i++) { total += actualA[i] * b[len - i - 1]; }
		System.out.println(total);
	}
}
len_ = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
 
subarr_num = [(i + 1) * (len_ - i) for i in range(len_)]
 
actual_a = [i * j for i, j in zip(subarr_num, a)]
 
actual_a.sort()
b.sort(reverse=True)
 
total = sum(i * j for i, j in zip(actual_a, b))
print(total)
Fundamentos