19960. Telemarketing

Olá meus amigos nerds, em primeiro lugar desculpem-me por meu hiato, na última semana estive trabalhando, juntamente com alguns amigos, em um sistema de recomendação de problemas para o spoj e acabei ficando sem tempo de conversar com vocês.

Hoje vamos contar quantas ligações faz um atendente de telemarketing, já que é isso que o problema 19960. Telemarketing nos pede.

O problema nos fornece uma lista de ligações que devem ser feitas na ordem fornecida, juntamente com o tempo necessário para se fazer cada ligação e nos pede que contemos quantas ligações cada um dos n atendentes de telemarketing devem fazer.

Solução

Lendo o problema, é possível perceber que para saber quantas ligações cada atendente fez é necessário simularmos as ligações feitas. O problema então reside em fazer essa simulação de modo eficiente.

Uma forma simples de simularmos as ligações é simularmos o que ocorre em cada instante de tempo, obviamente simular cada instante de tempo além de ser desnecessário é muito custoso. Felizmente, podemos restringir nossa simulação a dois momentos:

• inicio de uma ligação - momento que um vendedor se torna indisponível
• fim de uma ligação - momento em que um vendedor se torna ocioso

O seguinte algoritmo realiza a simulação, onde uma fila de prioridades é usada para manter de modo eficiente qual será o próximo vendedor ocioso (e portanto o responsável por fazer a ligação)

Seja Ti o tempo gasto em ligações pelo vendedor i.
para cada vendedor
   Ti = 0
Adicione cada vendedor a fila de prioridade f, ordenada pelo tempo Ti
para cada ligação
   Seja v o vendedor que está no topo da fila
   Esse vendedor realiza essa ligação (incremente o número de ligações que ele fez)
   Seja Tl o tempo da ligação
   Ti += Tl

Esse tipo de simulação apresentada no algoritmo acima é conhecida como simulação de eventos discretos (você pode saber mais sobre ela aqui).

Implementação

Observe que usei apenas inteiros nessa simulação, já que 30*1.000.000 cabe em 32 bits (int).