1340 - Eu Posso Adivinhar a Estrutura de Dados!
Um dos meus problemas favoritos da plataforma!
Descrição
Solução
Esse problema é bem legal porque você pode implementar as três estruturas de dados e ir simulando cada uma das operações em cada estrutura de cada vez. Se a operação 2 daria erro (importante prever antes de fazer a operação) ou não obtiver o elemento esperado pela entrada, então simplesmente paramos de interagir com aquela estrutura de dados específica.
Mesmo que tenhamos descartado todas as estruturas de dados da resposta, ainda precisamos ler a entrada até o final para não confundir casos de teste diferentes.
O heap implementado na biblioteca em Python ordena do menor para o maior elemento. Logo, tivemos que colocar os elementos com valor negativo para que a ordem fosse a mesma pedida no enunciado.
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main()
{
bool p, f, fp;
queue<int> fila;
stack<int> pilha;
int n, operacao, numero;
priority_queue<int> filaPrioridade;
while (cin >> n)
{
while (!pilha.empty())
pilha.pop();
while (!fila.empty())
fila.pop();
while (!filaPrioridade.empty())
filaPrioridade.pop();
p = true, f = true, fp = true;
for (int i = 0; i < n; ++i)
{
cin >> operacao >> numero;
if (operacao == 1)
{
if (p)
pilha.push(numero);
if (f)
fila.push(numero);
if (fp)
filaPrioridade.push(numero);
}
else
{
if (p)
{
if (pilha.empty() || pilha.top() != numero)
p = false;
else
pilha.pop();
}
if (f)
{
if (fila.empty() || fila.front() != numero)
f = false;
else
fila.pop();
}
if (fp)
{
if (filaPrioridade.empty() || filaPrioridade.top() != numero)
fp = false;
else
filaPrioridade.pop();
}
}
}
if (p && !f && !fp)
cout << "stack" << endl;
else if (!p && f && !fp)
cout << "queue" << endl;
else if (!p && !f && fp)
cout << "priority queue" << endl;
else if (!p && !f && !fp)
cout << "impossible" << endl;
else
cout << "not sure" << endl;
}
return 0;
}
Last updated
Was this helpful?