Skip to Content
CTRL K

Matching

Explicación

La fórmula dada para añadir una arista puede parecer un poco rara, pero la observación clave es que podemos convertirla en lo siguiente con un poco de manipulación algebraica:

i−ai=j−aj i-a_i=j-a_j

A partir de esto podemos dar a cada nodo una especie de “ID”, y solo los nodos con IDs idénticos se pueden enlazar. En otras palabras, nuestro grafo global consistirá en un montón de conjuntos de nodos que están todos conectados dos a dos.

Dentro de estos grupos de nodos, intentamos emparejar tantos pares de peso positivo como sea posible. Hay muchas formas de hacerlo; en mi implementación los ordené de forma descendente y emparejé todos los pares adyacentes.

Implementación

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

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int len;
		std::cin >> len;
		vector<int> arr(len);
		for (int &i : arr) { std::cin >> i; }
 
		std::map<int, vector<int>> groups;
		for (int i = 0; i < arr.size(); i++) {
			int id = i - arr[i];
			groups[id].push_back(arr[i]);
		}
 
		long long total = 0;
		for (auto &comp : groups) {
			std::sort(comp.second.rbegin(), comp.second.rend());
			for (int i = 0; i + 1 < comp.second.size(); i += 2) {
				int weight = comp.second[i] + comp.second[i + 1];
				if (weight > 0) { total += weight; }
			}
		}
 
		cout << total << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class Matching {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			read.readLine();
			int[] arr = Arrays.stream(read.readLine().split(" "))
			                .mapToInt(Integer::parseInt)
			                .toArray();
 
			Map<Integer, List<Integer>> groups = new HashMap<>();
			for (int i = 0; i < arr.length; i++) {
				int id = i - arr[i];
				groups.putIfAbsent(id, new ArrayList<>());
				groups.get(id).add((Integer)arr[i]);
			}
 
			long total = 0;
			for (List<Integer> comp : groups.values()) {
				comp.sort(Comparator.reverseOrder());
				for (int i = 0; i + 1 < comp.size(); i += 2) {
					int weight = comp.get(i) + comp.get(i + 1);
					if (weight > 0) { total += weight; }
				}
			}
 
			System.out.println(total);
		}
	}
}
for _ in range(int(input())):
	input()
	arr = [int(i) for i in input().split()]
 
	groups = {}
	for i in range(len(arr)):
		id_ = i - arr[i]
		if id_ not in groups:
			groups[id_] = []
		groups[id_].append(arr[i])
 
	total = 0
	for comp in groups.values():
		comp.sort(reverse=True)
		for i in range(0, len(comp) - 1, 2):
			weight = comp[i] + comp[i + 1]
			if weight > 0:
				total += weight
 
	print(total)
Fundamentos