Solução Telemarketing

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

 

Para resolver esse problema, vamos precisar criar nossa própria struct com operadores "<" e ">". Também vamos usar a priority_queue, da biblioteca queue, uma estrutura de dados já implementada pelo C++ que simula uma heap, ou seja, mantêm elementos em uma fila ordenada, adicionando (push) ou removendo (pop) elementos da fila em O(\log{n}) e retornando o primeiro elemento da fila em O(1). Se você não conhece essa estrutura, clique aqui para ver a aula do Noic sobre heap.

A ideia é manter os atendentes ordenados em uma fila de prioridade pelo horário em que ficarão livres, depois pelo seu número de identificação. Assim, vamos percorrer todas as ligações, sempre atribuindo cada uma ao atendente da frente da fila de prioridade, pois ele será o primeiro que ficou livre, e em caso de empate, é o de menor identificação.

Para implementar isso, vamos primeiro criar a struct atendente. Ela terá dois inteiros: int idint livre, que representam, respectivamente, o número de identificação do atendente e o horário em que ele ficará livre. O operadores "<" e ">" deve comparar primeiro pelo elemento livre dos alunos, depois pelo elemento id. Note ainda que devemos declarar como maior o elemento que vem antes na fila de prioridade (pois a priority_queue mantêm os elementos ordenados do maior para o menor), logo o menor deve ser o de maiores livre id, enquanto que o maior deve ser o de menores livre id (para que venha primeiro na fila de prioridade). Vamos criar também o array int qtd[MAXN], que irá salvar, na posição i, o número de ligações atendidas pelo atendente com identificação de número i.

Criada a struct aluno e declarada a priority_queue<aluno> heap; (seu nome será heap), vamos ler, uma a uma, a duração t de cada ligação e atribuir cada uma ao primeiro atendente livre. Para isso, vamos fazer uma variável que representará em que minuto estamos. Seu nome será tempo e ela ficará fora do loop, começando com o valor 0. Para cada ligação lida, vamos atribuí-la ao atendente davez, que será o primeiro da fila de prioridade ("atendente davez=heap.top();"). Assim, vamos retirá-lo da frente da fila ("heap.pop();") e adicionar uma ligação à quantidade de ligações atendidas por esse atendente ("qtd[davez.id]++;"). Feito isso, se a ligação teve que esperar para ser atendida, ou seja, se davez só fica livre depois do minuto atual ("if(davez.livre>tempo)"), devemos adiantar o tempo até a hora de seu atendimento, que ocorreu no minuto em que davez ficou livre ("tempo=davez.livre;"). Agora, basta salvarmos que ele só ficará livre após minutos ("davez.livre+=t;") e reinserirmos o atendente na fila de prioridade ("heap.push(davez);").

Após termos lido toda a entrada, basta percorremos o vetor qtd, imprimindo a posição (identificação do atendente) e o valor nele salvo (número de ligações que ele atendeu) para cada um dos elementos de qtd. Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: