Kites

Explicación

Debemos obtener $2$ pares de números iguales. Para que dos índices $i_1$ e $i_2$ contengan el mismo valor, se necesitan $|sticks[i_1]-sticks[i_2]|$ operaciones. Por lo tanto, es óptimo ordenar el arreglo y hacer iguales pares adyacentes de números.

Así, ordenamos el arreglo de entrada y calculamos $diff[i]=sticks[i+1]-sticks[i]$ para $0<i<n-1$ . El problema se reduce ahora a elegir dos índices $i_1$ e $i_2$ tales que $diff[i_1]+diff[i_2]$ sea mínimo. Sin embargo, los dos pares no pueden compartir ningún número, así que $i_1$ e $i_2$ no pueden ser adyacentes entre sí (si $i_2=i_1+1$ , los pares serían $i_1, i_1+1$ e $i_1+1, i_1+2$ , que se solapan).

Sin pérdida de generalidad, $i_1 < i_2$ . Recorremos $2\leq i_2<n-1$ (pues $i_2=1$ es imposible). Al fijar $diff[i_2]$ , $i_1$ debe estar en $1\leq i_1<i_2-1$ , y podemos mantener un mínimo de prefijos de $diff[i_1]$ para obtener el mejor $diff[i_1]$ para cada $i_2$ .

Implementación

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

C++Java


#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
 
using namespace std;
 
void solve() {
	int n;
	cin >> n;
 
	vector<int> sticks(n);
	for (int i = 0; i < n; i++) cin >> sticks[i];
	sort(sticks.begin(), sticks.end());
 
	vector<int> diff(n - 1);
	for (int i = 0; i < n - 1; i++) diff[i] = sticks[i + 1] - sticks[i];
 
	int ans = INT_MAX;
	int min_previous_diff = diff[0];
	// Loop over i_2
	for (int i = 2; i < n - 1; i++) {
		ans = min(ans, diff[i] + min_previous_diff);
		// diff[i+1] can be combined with anything before diff[i].
		min_previous_diff = min(min_previous_diff, diff[i - 1]);
	}
	cout << ans << endl;
}
 
int main() {
	int test_num;
	cin >> test_num;
	for (int i = 0; i < test_num; i++) solve();
	return 0;
}


import java.io.*;
import java.util.*;
 
public class Kites {
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
 
		for (int t = 0; t < testNum; t++) {
			int n = io.nextInt();
			int[] sticks = new int[n];
			int[] diff = new int[n - 1];
 
			for (int i = 0; i < n; i++) { sticks[i] = io.nextInt(); }
 
			Arrays.sort(sticks);
 
			for (int i = 0; i < n - 1; i++) { diff[i] = sticks[i + 1] - sticks[i]; }
 
			int ans = Integer.MAX_VALUE;
			int minPreviousDiff = diff[0];
 
			// Loop over i_2
			for (int i = 2; i < n - 1; i++) {
				ans = Math.min(ans, diff[i] + minPreviousDiff);
				// diff[i+1] can be combined with anything before diff[i].
				minPreviousDiff = Math.min(minPreviousDiff, diff[i - 1]);
			}
 
			io.println(ans);
		}
		io.close();
	}
 
	// BeginCodeSnip{Kattio}
}