Solução por Pedro Racchetti
Conteúdos Utilizados:
Para esse problema, podemos utilizar dois $$multisets$$, 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:
| #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; | |
| } |
