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 
e retornando o primeiro elemento da fila em 
. 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 id e int 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 e id, enquanto que o maior deve ser o de menores livre e 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 t 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:
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 <cstdio> | |
| #include <queue> | |
| #define MAXN 1010 | |
| #define MAXL 1000100 | |
| using namespace std; | |
| int n, l, t, qtd[MAXN]; | |
| struct atendente{ // declaro a struct atendente | |
| int id, livre; // ela terá dois inteiros como membros | |
| // terá um construtor para atribuir valores aos membros | |
| atendente(int id_, int livre_=0){ id=id_; livre=livre_; } | |
| // terá também um operador >, para compará-la com outro atendente | |
| // note que a priority_queue ordena do maior para o menor | |
| // logo este operador deve retornar true se a struct vem antes na ordenação | |
| bool operator >(const atendente x) const{ | |
| // se eles ficarem livres em momentos diferentes | |
| if(livre!=x.livre) return livre<x.livre; // ele retorna o que fica livre antes | |
| return id<x.id; // caso contrário, retorna o de menor id | |
| } | |
| // crio também o operador < de maneira análoga ao > | |
| bool operator <(const atendente x) const{ | |
| if(livre!=x.livre) return livre>x.livre; | |
| return id>x.id; | |
| } | |
| }; | |
| priority_queue<atendente> heap; // crio a priority_queue de atendente de nome "heap" | |
| int main(){ | |
| scanf("%d %d", &n, &l); // leio os valores de n e l | |
| for(int i=1; i<=n; i++) heap.push(atendente(i)); // insiro os atendentes na fila de prioridade | |
| int tempo=0; // inicializo tempo com o valor 0 | |
| for(int i=1; i<=l; i++){ // para cada ligação | |
| scanf("%d", &t); // leio sua duração | |
| atendente davez=heap.top(); // e vejo qual o atendente que irá atendê-la (o primeiro de heap) | |
| heap.pop(); // tiro ele do topo | |
| qtd[davez.id]++; // e aumento a quantidade de ligações por ele atendidas | |
| if(davez.livre>tempo) tempo=davez.livre; // se a ligação teve que esperar, atualizo o tempo | |
| davez.livre+=t; // salvo que o atendente davez só ficará livre novamente em t minutos | |
| heap.push(davez); // e o reinsiro na fila de prioridade | |
| } | |
| // depois, para cada um dos atendentes, imprimo sua identificação e a quantidade de ligações atendidas | |
| for(int i=1; i<=n; i++) printf("%d %d\n", i, qtd[i]); | |
| return 0; | |
| } |