Skip to Content
CTRL K

Dima and Containers

Explicación

En lugar de procesar cada comando uno por uno, podemos procesar cada operación de adición cuando tengamos que extraer nuestros números. Esto nos da más previsión a la hora de decidir qué números priorizar.

Si tenemos ≤3\leq 3 elementos para procesar, entonces ponemos de forma arbitraria cada elemento en un contenedor vacío, y hacemos pop de esos contenedores respectivos.

Entre los tres tipos de contenedores, el deque es el más flexible en cuanto a operaciones. Por otro lado, la pila y la cola son relativamente inflexibles. Como estamos procesando todos los comandos de adición de una vez, podemos identificar los tres elementos más grandes que se han añadido y priorizarlos.

Para los dos elementos más grandes, podemos colocarlos en nuestra pila y cola cuando los encontremos. Para nuestro tercer elemento más grande, la estrategia es mantenerlo siempre en el frente o en el fondo una vez que lo insertamos en el deque, y colocar cualquier elemento nuevo en el lado opuesto. Esto garantiza que siempre podemos extraer los tres elementos más grandes insertados.

Implementación

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

#include <bits/stdc++.h>
 
using ll = long long;
 
int main() {
	int n;
	std::cin >> n;
 
	std::vector<int> nums;
	std::priority_queue<int> best;
	for (int i = 0; i < n; i++) {
		int a;
		std::cin >> a;
 
		if (a == 0) {
			// llevamos la cuenta de los 3 elementos más grandes
			std::multiset<int> top3;
			for (int i = 0; i < 3; i++) {
				if (best.empty()) { continue; }
				top3.insert(best.top());
				best.pop();
			}
 
			bool stack_used = false;
			bool queue_used = false;
			bool deque_used = false;
			std::vector<std::string> ops;
 
			for (int x : nums) {
				if (!top3.contains(x)) {
					std::cout << "pushBack\n";
					continue;
				}
 
				if (!stack_used) {
					std::cout << "pushStack\n";
					ops.push_back("popStack");
					stack_used = true;
				} else if (!queue_used) {
					std::cout << "pushQueue\n";
					ops.push_back("popQueue");
					queue_used = true;
				} else if (!deque_used) {
					std::cout << "pushFront\n";
					ops.push_back("popFront");
					deque_used = true;
				}
 
				// hay que borrar este elemento de top3; si no, podríamos
				// considerarlo más tarde por accidente cuando ya no cuenta
				top3.erase(top3.find(x));
			}
 
			std::cout << ops.size();
			for (const std::string &op : ops) { std::cout << ' ' << op; }
			std::cout << '\n';
 
			nums.clear();
			while (!best.empty()) { best.pop(); }
		} else {
			nums.push_back(a);
			best.push(a);
		}
	}
 
	// si nuestra última operación no es un 0, hay que procesar los nums restantes
	for (int i = 0; i < nums.size(); i++) { std::cout << "pushBack\n"; }
}
import java.io.*;
import java.util.*;
 
public class DimaContainers {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int n = Integer.parseInt(r.readLine());
 
		List<Integer> nums = new ArrayList<>();
		PriorityQueue<Integer> best = new PriorityQueue<>(Collections.reverseOrder());
 
		for (int i = 0; i < n; i++) {
			int a = Integer.parseInt(r.readLine());
 
			if (a == 0) {
				// llevamos la cuenta de los 3 elementos más grandes
				List<Integer> top3 = new ArrayList<>();
				for (int j = 0; j < 3; j++) {
					if (best.isEmpty()) { continue; }
					top3.add(best.poll());
				}
 
				boolean stackUsed = false;
				boolean queueUsed = false;
				boolean dequeUsed = false;
				List<String> ops = new ArrayList<>();
 
				for (int x : nums) {
					if (!top3.contains(x)) {
						pw.println("pushBack");
					} else {
						if (!stackUsed) {
							pw.println("pushStack");
							ops.add("popStack");
							stackUsed = true;
						} else if (!queueUsed) {
							pw.println("pushQueue");
							ops.add("popQueue");
							queueUsed = true;
						} else if (!dequeUsed) {
							pw.println("pushFront");
							ops.add("popFront");
							dequeUsed = true;
						}
 
						// hay que borrar este elemento de top3; si no, podríamos
						// considerarlo más tarde por accidente cuando ya no cuenta
						top3.remove((Integer)x);
					}
				}
 
				pw.print(ops.size());
				for (String op : ops) { pw.print(" " + op); }
				pw.println();
 
				nums.clear();
				best.clear();
			} else {
				nums.add(a);
				best.add(a);
			}
		}
 
		// si nuestra última operación no es un 0, hay que procesar los nums restantes
		for (int i = 0; i < nums.size(); i++) { pw.println("pushBack"); }
 
		r.close();
		pw.close();
	}
}
operations = []
nums = []
 
for _ in range(int(input())):
	i = int(input())
 
	if i == 0:
		# llevamos la cuenta de los 3 elementos más grandes
		top3 = sorted(nums)[-3:]
 
		stack_used = False
		queue_used = False
		deck_used = False
 
		for n in nums:
			if n in top3:
				if not stack_used:
					stack_used = True
					operations.append("pushStack")
				elif not queue_used:
					queue_used = True
					operations.append("pushQueue")
				elif not deck_used:
					deck_used = True
					operations.append("pushFront")
 
				# hay que borrar este elemento de top3; si no, podríamos
				# considerarlo más tarde por accidente cuando ya no cuenta
				top3.remove(n)
			else:
				operations.append("pushBack")
 
		nums = []
 
		operations.append(stack_used + queue_used + deck_used)
		if stack_used:
			operations.append("popStack")
		if queue_used:
			operations.append("popQueue")
		if deck_used:
			operations.append("popFront")
	else:
		nums.append(i)
 
# si nuestra última operación no es un 0, hay que procesar los nums restantes
for _ in range(len(nums)):
	operations.append("pushBack")
 
print("\n".join(str(o) for o in operations))
Fundamentos