Exercicio da regina

mercadinho.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* Elementos da fila */
typedef struct Fila{
    char nome[50];
    int tempo_chegada;
    int quantidade_produtos;
    struct Fila* prox;
} TFila;
typedef TFila* PFila;


/* Descritor de fila */
typedef struct{
    int total_produtos;
    int total_produtos_ultimo;
    int total_clientes;
    int total_clientes_max;
    PFila inicio;
    PFila fim;
} TFila_desc;
typedef TFila_desc* PFila_desc;


/* Descritor de caixa */
typedef struct Caixa{
    int constante;
    int clientes_atendidos;
    PFila_desc fila;
    struct Caixa* prox;
} TCaixa;
typedef TCaixa* PCaixa;


int abs(int x){
    if(x > 0)
        return x;
    else
        return x * (-1);
}

PFila_desc aloca_fila_desc(){
    PFila_desc novo = malloc(sizeof(TFila_desc));

    novo->inicio = NULL;
    novo->fim = NULL;
    novo->total_produtos = 0;
    novo->total_produtos_ultimo = 0;
    novo->total_clientes = 0;
    novo->total_clientes_max = 0;

    return novo;
}

PCaixa aloca_caixa(){
    PCaixa novo = malloc(sizeof(TCaixa));

    novo->fila = aloca_fila_desc();
    novo->prox = NULL;
    novo->clientes_atendidos = 0;

    return novo;
}

PFila aloca_cliente(){
    PFila novo = malloc(sizeof(TFila));

    novo->prox = NULL;

    return novo;
}

void insere_em_caixa(PFila cliente, PCaixa caixa){
    if(caixa->fila->inicio == NULL){
        caixa->fila->inicio = cliente;
        caixa->fila->fim = cliente;
    }
    else{
        caixa->fila->fim->prox = cliente;
        caixa->fila->fim = cliente;
    }
	cliente->prox = NULL;
    caixa->fila->total_produtos += cliente->quantidade_produtos;
    caixa->fila->total_produtos_ultimo = cliente->quantidade_produtos;
    caixa->fila->total_clientes_max += 1;
    caixa->fila->total_clientes += 1;
}

void insere_em_fila_desc(PFila cliente, PFila_desc fila){
    if(fila->inicio == NULL){
        fila->inicio = cliente;
        fila->fim = cliente;
    }
    else{
        fila->fim->prox = cliente;
        fila->fim = cliente;
    }
}

PFila remove_de_caixa(PCaixa caixa){
    PFila aux;

    if(caixa->fila->inicio == NULL){
        return NULL;
    }
    else{
        aux = caixa->fila->inicio;
        caixa->fila->inicio = aux->prox;

        if(caixa->fila->inicio == NULL){
            caixa->fila->total_produtos_ultimo = 0;
        }
		else{
			caixa->fila->total_produtos_ultimo = caixa->fila->inicio->quantidade_produtos;
		}

        caixa->fila->total_clientes -= 1;

        return aux;
    }
}

void insere_cliente(PFila cliente, PCaixa caixas){
    PCaixa menor_fila, aux;
    menor_fila = caixas;
    int i, j;

    for(aux=caixas, i=0, j=0; aux != NULL; aux = aux->prox, j++){
        if(aux->fila->total_clientes < menor_fila->fila->total_clientes){
            menor_fila = aux;
            i = j;
        }
        else if(aux->fila->total_clientes == menor_fila->fila->total_clientes &&
                aux->fila->total_produtos_ultimo < menor_fila->fila->total_produtos_ultimo){
            menor_fila = aux;
            i = j;
        }
    }

    //printf("Inserindo %s em caixa %d\n", cliente->nome, i+1);
    insere_em_caixa(cliente, menor_fila);
}

bool acabou_tudo(PFila_desc clientes, PCaixa caixas){
    bool todos_caixas_vazios = true;
    PCaixa aux2;

    for(aux2 = caixas; aux2 != NULL && todos_caixas_vazios; aux2 = aux2->prox){
        if(aux2->fila->inicio != NULL){
            todos_caixas_vazios = false;
        }
    }

    if(clientes->inicio == NULL && todos_caixas_vazios){
        return true;
    }
    else{
        return false;
    }
}

bool processador(PFila cliente, PCaixa caixa, int tempo_atual, int tempo_saida_ultimo){
    int tempo_final;

    if(cliente == NULL){
        return false;
    }

    tempo_final = 10 + (cliente->tempo_chegada) +
            (cliente->quantidade_produtos) * (caixa->constante);

    if(cliente->tempo_chegada < tempo_saida_ultimo){
        tempo_final += abs((cliente->tempo_chegada) - tempo_saida_ultimo);
    }

    if(tempo_final > tempo_atual){
        return false;
    }
    else{
        return true;
    }
}

int main(){
    int flag, quantidade_caixas, i;
    int quantidade_clientes, tempo_saida_ultimo;

    PCaixa caixas = NULL;
    PCaixa novo, auxiliar;

    PFila_desc clientes = aloca_fila_desc();
    PFila novo_cliente, aux;

    scanf("%d", &flag);
    scanf("%d", &quantidade_caixas);

    for(i=0; i<quantidade_caixas; i++){
        novo = aloca_caixa();
        scanf("%d", &(novo->constante));

        if(caixas == NULL){
            caixas = novo;
        }
        else{
            for(auxiliar=caixas; auxiliar->prox != NULL; auxiliar = auxiliar->prox);
            auxiliar->prox = novo;
        }
    }

    scanf("%d", &quantidade_clientes);

    for(i=0; i<quantidade_clientes; i++){
        novo_cliente = aloca_cliente();
        scanf("%s", &(novo_cliente->nome));
        scanf("%d", &(novo_cliente->tempo_chegada));
        scanf("%d", &(novo_cliente->quantidade_produtos));
        insere_em_fila_desc(novo_cliente, clientes);
   }


    tempo_saida_ultimo = 0;
    for(i=0; !acabou_tudo(clientes, caixas); i++){

       /* Verifica se temos que remover alguem dos caixas */
        for(novo = caixas; novo != NULL; novo = novo->prox){
            if(processador(novo->fila->inicio, novo, i, tempo_saida_ultimo)){
                novo_cliente = remove_de_caixa(novo);
                tempo_saida_ultimo = i;
                if(flag == 1){
                    printf("Removido: %s %d %d\n", novo_cliente->nome, novo_cliente->tempo_chegada, i);
                }
            }
        }

        /* Coloca o cliente atual na fila adequada */
        if(clientes->inicio != NULL && i == clientes->inicio->tempo_chegada){
			aux = clientes->inicio->prox;
            insere_cliente(clientes->inicio, caixas);
            clientes->inicio = aux;
        }


    }


    if(flag == 2){
        for(novo = caixas, i=1; novo != NULL; novo = novo->prox, i++){
            printf("Caixa #%d: %d %d\n", i, novo->fila->total_clientes_max,
                    novo->fila->total_produtos);
        }
    }

    return 0;
}