Solução por Samyra Almeida
Conhecimento prévio necessário:
Bem, no início iremos adicionar na priority queue os $$N$$ caixas com tempo igual a $$0$$, pois nenhum dos mesmos realizou algum atendimento.
Note que, o $$i$$-ésimo cliente será atendido pelo primeiro caixa que ficar disponível, e como nossa priority queue ordena os tempos de atendimento dos caixas em ordem crescente, podemos concluir que o caixa que estiver no topo da fila sempre atenderá o $$i$$-ésimo cliente.
Com isso, para cada um dos clientes, basta tirarmos o caixa que está no topo da fila e primeiro checamos se ele fica “livre” antes do cliente chegar, ou seja, tempo do caixa é melhor que o tempo que o cliente chegou na fila. Se sim adiciono a diferença entre o tempo do cliente e o do caixa ao tempo do caixa. E depois checamos se a diferença entre o tempo do caixa e o tempo que o $$i$$-ésimo cliente chega na fila do banco é maior que $$20$$, se sim, incremento a resposta em uma unidade. Depois adiciono $$d$$ (duraçao do atendimento do $$i$$-ésimo cliente) ao tempo do caixa e o adiciono novamente a priority queue.
Ao final, basta imprimir a resposta.
Para maior compreensão leia o código-solução abaixo:
| // NOIC – Problemas da Semana 69 – Iniciante | |
| // Solução por Samyra Almeida | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| int c, n, resp; | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); | |
| cin >> c >> n; | |
| priority_queue<ll, vector<ll>, greater<ll> > caixas; | |
| for(int i = 1 ; i <= c ; ++i) caixas.push(0); // adiciono todos os caixas na priority queue | |
| for(int i = 0 ; i < n ; ++i) | |
| { | |
| ll tempo_caixa = caixas.top(); // tiro o caixa que esta no topo da fila. | |
| caixas.pop(); | |
| ll t, d; | |
| cin >> t >> d; | |
| if(tempo_caixa < t) tempo_caixa += (t – tempo_caixa); // checo se o caixa fila "livre" por algum tempo. | |
| if(tempo_caixa – t > 20) resp++; // se o cliente passou mais de 20 minutos esperando, incremento a resposta | |
| tempo_caixa += d; // atualizo o tempo de atendimento do caixa | |
| caixas.push(tempo_caixa); // o coloco novamente na fila | |
| } | |
| cout << resp << "\n"; // imprimo a resposta | |
| } |
