Cod sursa(job #460950)

Utilizator hodoo_manrazvan ionita hodoo_man Data 4 iunie 2010 19:57:51
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 4.02 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct g
{
    unsigned int inainte;
    unsigned int greu;
}gutui;

int compare (const void *x, const void *y)
{
    if ((*(gutui*)x).inainte == (*(gutui*)y).inainte)
        return -((*(gutui*)x).greu - (*(gutui*)y).greu);
    else 
        return -((*(gutui*)x).inainte - (*(gutui*)y).inainte);        
}

int main()
{
    FILE *f, *g;
    f = fopen ("gutui.in", "r");
    g = fopen ("gutui.out", "w");
    
    unsigned int n, h, u, i, nivel=0, total=0, heap[100001], dim=0, aux;
    fscanf (f, "%u", &n);
    fscanf (f, "%u", &h);
    fscanf (f, "%u", &u);
    gutui gt[n];
    for (i=0; i<n; i++)
    {
        fscanf (f, "%u", &gt[i].inainte);
        fscanf (f, "%u", &gt[i].greu);
        gt[i].inainte = (h - gt[i].inainte) / u; //cate gutui poate gigel culege inainte
    }    

    fclose (f); 
    
    qsort(gt, n, sizeof(gutui), compare);
    //sortam crescator in fct de "etaj" si descrescator in fct de greutate
    if (gt[0].inainte == 0)
    {
        fprintf(g, "%u", gt[0].greu);
        fclose(g);
        return 0;
    }
    
    nivel = gt[0].inainte;
    total = gt[0].greu;
    heap[0] = 0;

    for (i=1; i<n; i++)
    {
        //introducem in heap
        dim++;
        heap[dim] = gt[i].greu;
        //urcam elementul daca e cazul
        unsigned curent = dim;
        while ((heap[curent] > heap[(curent / 2)]) && (curent > 1))
        {
            //interschimbam cu parintele
            aux = heap[curent / 2];
            heap[curent / 2] = heap[curent];
            heap[curent] = aux;
            curent = curent / 2;
        }
        
        
        while (gt[i].inainte < nivel && (dim > 0))
        {
            nivel--;
            //scoatem greutatea din varf
            total += heap[1];
            
            //si punem in locul ei cea mai din dreapta greutate de pe ultimul nivel
            heap[1] = heap[dim];
            dim--;
            //coboram greutatea din varf
            int ok = 1;
            unsigned int curent = 1;
            while (ok)
            {
                //verificam daca trebuie inlocuit cu fiul din stanga sau dreapta
                unsigned int deschimbat = curent;
                unsigned int stanga = 2 * curent;
                unsigned int dreapta = 2 * curent + 1;
                if ((stanga <= dim) && (heap[stanga] > heap[curent]))
                    deschimbat = stanga;
                if ((dreapta <= dim) && (heap[dreapta] > heap[deschimbat]))
                    deschimbat = dreapta;
                
                if (deschimbat != curent)
                {
                    aux = heap[curent];
                    heap[curent] = heap[deschimbat];
                    heap[deschimbat] = aux;
                    curent = deschimbat;
                }
                else
                    ok = 0;
            }
            if (nivel == 0)
                break;
            
        }
        nivel = gt[i].inainte;
        
    }
    
    while (nivel > 0 && dim > 0)
    {
        nivel--;
        
        total += heap[1];
            
        heap[1] = heap[dim];
        dim--;
        
        int ok = 1;
        unsigned int curent = 1;
        while (ok)
        {
            unsigned int deschimbat = curent;
            unsigned int stanga = 2 * curent;
            unsigned int dreapta = 2 * curent + 1;
            if ((stanga <= dim) && (heap[stanga] > heap[curent]))
                deschimbat = stanga;
            if ((dreapta <= dim) && (heap[dreapta] > heap[deschimbat]))
                deschimbat = dreapta;
                
            if (deschimbat != curent)
            {
                aux = heap[curent];
                heap[curent] = heap[deschimbat];
                heap[deschimbat] = aux;
                curent = deschimbat;
            }
            else
                ok = 0;
        }
    }
    
    
    fprintf(g, "%u", total);
    fclose(g);
    return 0;
}