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:
This file contains hidden or 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
| // 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 | |
| } |