OBI2012, Fase 2, Nível 2

banco-sergiosvieira.cc

#include <iostream>
#include <cstdio>
#include <queue>

/**
  Author: Sérgio Vieira - [email protected] - 2013
  Usage: banco < entrada.txt
**/

using namespace std;

class Client
{
public:
    int t;
    int d;
};

class Cashier
{
public:
    Client *client;
    int time; // instante  inicial de atendimento do cliente
};


int main()
{
	int maxTime = 10300; // pior caso todos os clientes chegam no tempo 3000. Tempo total para 1 caixa atender 1000 clientes com 10 minutos cada
    int maxDelay = 20;
    int c, n;
    int count = 0;
    queue<Client*> clients;

    if (scanf("%d %d", &c, &n) == 2)
    {
        int t, d;

        while(scanf("%d %d", &t, &d) == 2)
        {
            Client *aux = new Client();

            aux->t = t;
            aux->d = d;

            clients.push(aux);
        }

        Cashier cashiers[c];

        for (int i = 0; i < c; i++)
        {
            cashiers[i].client = NULL;
        }

        for (int i = 0; i <= maxTime; i++)
        {
            for (int j = 0; j < c; j++)
            {
                Client *aux = cashiers[j].client;

                if (aux == NULL)
                {
                    if (clients.empty())
                    {
                        cashiers[j].client = NULL;
                    }
                    else
                    {
                        cashiers[j].client = clients.front();
                        clients.pop();
                        cashiers[j].time = i;
                    }
                }
                else if (cashiers[j].time + aux->d == i)
                {
                    if (cashiers[j].time - aux->t > maxDelay)
                    {
                        count++;
                    }

                    delete aux;

                    if (clients.empty())
                    {
                        cashiers[j].client = NULL;
                    }
                    else
                    {
                        cashiers[j].client = clients.front();
                        clients.pop();
                        cashiers[j].time = i;
                    }
                }
            }

        }
    }

    cout << count << "\n";

	return 0;
}