Array Destruction
Implementación
Complejidad temporal:
// 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]); }
}
}
}
}