Solução por Pedro Racchetti
Conteúdos Utilizados:
Para esse problema, podemos utilizar dois 
, um para manter os números menores que a mediana, e um para manter os números maiores que a mediana. Para isso, guardaremos quantos números no total estamos analisando.
Quando recebermos uma bolacha nova, e o total de números for ímpar, basta inserir-lo na estrutura de números maiores, e trazer o menor número dela para a estrutura de números menores, e então aumentar o total de números. Caso o total de números for par, faremos o processo contrário, inserindo o número na estrutura de menores, e passando o maior número dessa estrutura para a estrutura de maiores.
Com isso, podemos perceber que para calcularmos a mediana, basta usarmos o menor número da estrutura dos maiores, e então removê-lo. Porém, para mantermos essa propriedade, quando o total de números for par antes de remover, precisaremos mover o maior número da estrutura dos maiores para a estrutura dos menores, já que essa será a mediana agora.
Segue o código, comentado, para melhor compreensão:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| int tot; //total de inteiros sendo analisados | |
| string s;//string auxiliar para ler a entrada | |
| multiset<int> menores, maiores; | |
| int main(){ | |
| while(cin >> s){ //leremos até acabar a entrada | |
| if(s[0] == '#'){ | |
| if(tot % 2==0){ | |
| printf("%d\n",*maiores.begin()); //pelo método que usamos, a mediana sempre será o menor valor dos maiores | |
| maiores.erase(maiores.begin()); | |
| multiset<int>::iterator it=menores.end(); | |
| it--; | |
| maiores.insert(*it); | |
| menores.erase(it); //rebalanceamos as estruturas, para garantir a proprieadade da mediana. | |
| }else{ | |
| printf("%d\n",*maiores.begin()); | |
| maiores.erase(maiores.begin());//não é necessario rebalancear, | |
| //ja que agora ambas as estruturas terão a mesma quantia de números | |
| } | |
| tot--; //como retiramos um valor, podemos subtrair o total | |
| } | |
| else{ | |
| int i = stoi(s); //convertemos a string para um número | |
| if(tot%2==0){ | |
| menores.insert(i); | |
| multiset<int>::iterator it=menores.end(); | |
| it--; | |
| maiores.insert(*it); //inserimos o numero na estrutura menor, e rebalanceamos para garantir a propriedade | |
| menores.erase(it); | |
| }else{ | |
| maiores.insert(i); | |
| menores.insert(*maiores.begin()); | |
| maiores.erase(maiores.begin()); | |
| //inserimos o numero na estrutura maior, e rebalanceamos para garantir a propriedade | |
| //para garantir que ambas as estruturas tenham o mesmo tamanho. | |
| } | |
| tot++; | |
| } | |
| } | |
| return 0; | |
| } |