Solução Informática Iniciante - Semana 69

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
}