Skip to Content

Array Destruction

Editorial oficial 

Implementación

Complejidad temporal: O(N2logN)\mathcal{O}(N^2\log N)

// iostream, vector, set, and algorithm #include <bits/stdc++.h> using namespace std; const int MAX_SIZE = 2000; int arr_size; int arr[MAX_SIZE]; vector<pair<int, int>> pair_to_remove; bool works(int initial_sum) { pair_to_remove.clear(); // Este multiconjunto guarda todos los elementos no destruidos multiset<int> remaining; for (int i = 0; i < arr_size; i++) { remaining.insert(arr[i]); } while (remaining.size()) { // El elemento más grande que no ha sido eliminado int curr = *remaining.rbegin(); remaining.erase(remaining.find(curr)); // Si esta condición es cierta, entonces es imposible destruir el // arreglo con la suma inicial dada if (remaining.find(initial_sum - curr) == remaining.end()) { return false; } remaining.erase(remaining.find(initial_sum - curr)); pair_to_remove.push_back({curr, initial_sum - curr}); initial_sum = curr; } return remaining.empty(); } void solve() { cin >> arr_size; arr_size *= 2; for (int i = 0; i < arr_size; i++) { cin >> arr[i]; } sort(arr, arr + arr_size); for (int i = 0; i < arr_size - 1; i++) { // La suma inicial debe ser el elemento más grande del arreglo y arr[i] int initial_sum = arr[i] + arr[arr_size - 1]; /* * Basta comprobar si la suma inicial podría destruir el arreglo. * Luego, debemos imprimir la suma inicial y cada par de * elementos que destruimos. */ if (works(initial_sum)) { cout << "YES" << endl; cout << initial_sum << endl; for (pair<int, int> x : pair_to_remove) { cout << x.first << " " << x.second << endl; } return; } } cout << "NO" << endl; } int main() { int t; cin >> t; for (int i = 1; i <= t; i++) { solve(); } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.TreeMap; public final class DestroyArray { 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++) { int halfSize = Integer.parseInt(read.readLine()); TreeMap<Integer, Integer> nums = new TreeMap<>(); for (int i : Arrays.stream(read.readLine().split(" ")) .mapToInt(Integer::parseInt) .toArray()) { nums.put(i, nums.getOrDefault(i, 0) + 1); } int validStart = -1; ArrayList<int[]> validMoves = null; for (int toRemove : nums.keySet()) { int start = nums.lastKey() + toRemove; int at = start; TreeMap<Integer, Integer> remaining = new TreeMap<>(nums); ArrayList<int[]> moves = new ArrayList<>(); for (int i = 0; i < halfSize; i++) { int largest = remaining.lastKey(); remaining.put(largest, remaining.get(largest) - 1); if (remaining.get(largest) == 0) { remaining.remove(largest); } int other = at - largest; if (!remaining.containsKey(other)) { break; } at = largest; remaining.put(other, remaining.get(other) - 1); if (remaining.get(other) == 0) { remaining.remove(other); } moves.add(new int[] {largest, other}); } if (moves.size() == halfSize) { validStart = start; validMoves = moves; break; } } if (validMoves == null) { System.out.println("NO"); } else { System.out.printf("YES%n%d%n", validStart); for (int[] m : validMoves) { System.out.printf("%d %d%n", m[0], m[1]); } } } } }