Cod sursa(job #442509)

Utilizator hodoo_manrazvan ionita hodoo_man Data 14 aprilie 2010 18:33:43
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 4.19 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, max=0, nivel=0, total=0, heap[100001], dim=1, 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 putem culege inaintea ei
        if (gt[i].inainte > max)
            max = gt[i].inainte;
    }    

    fclose (f); 
    
    //in n citim, in n log n sortam, in n log n construim heapu
    qsort(gt, n, sizeof(gutui), compare);
    //for (i=0; i<n; i++)
    //    printf("%u %u\n", gt[i].inainte, gt[i].greu);
    
    if (max == 0)
    {
        fprintf(g, "%u", gt[0].greu);
    }
    for (i=0; i<n; i++)
    {
        //introduc in heap
        heap[dim-1] = gt[i].greu;
        //urc daca e cazul
        while ((dim > 1) && (heap[dim - 1] > heap[(dim - 2) / 2]))
        {
            //interschimb cu parintele
            aux = heap[(dim - 2) / 2];
            heap[(dim - 2) / 2] = heap[dim - 1];
            heap[dim - 1] = aux;
        }
        dim++;
        //printf ("%u\n", i);
        if (gt[i+1].inainte < gt[i].inainte) //daca am terminat cu un nivel
        {
            nivel++;
            //printf("gata nivelu %u\n", nivel);
            //scot greutatea din varf
            total += heap[0];
            dim--;
            //si pun in locul ei cea mai din dreapta greutate de pe ultimul nivel
            heap[0] = heap[dim - 1];
            //cobor greutatea din varf
            int ok = 1;
            unsigned int curent = 0;
            while (ok)
            {
                unsigned int deschimbat = curent;
                unsigned int stanga = 2 * curent + 1;
                unsigned int dreapta = 2 * curent + 2;
                if ((stanga < dim) && (heap[stanga] > heap[curent]))
                    deschimbat = stanga;
                if ((dreapta < dim) && (heap[dreapta] > heap[curent]))
                    deschimbat = dreapta;
                
                if (deschimbat != curent)
                {
                    aux = heap[curent];
                    heap[curent] = heap[deschimbat];
                    heap[deschimbat] = aux;
                    curent = deschimbat;
                }
                else
                    ok = 0;
            }
            if (nivel == (max + 1))
                break;
        }
    }
    
    while (nivel < (max + 1) && (dim > 0))
        {
            nivel++;
            //printf("gata nivelu %u\n", nivel);
            //scot greutatea din varf
            total += heap[0];
            dim--;
            //si pun in locul ei cea mai din dreapta greutate de pe ultimul nivel
            heap[0] = heap[dim - 1];
            //cobor greutatea din varf
            int ok = 1;
            unsigned int curent = 0;
            while (ok)
            {
                unsigned int deschimbat = curent;
                unsigned int stanga = 2 * curent + 1;
                unsigned int dreapta = 2 * curent + 2;
                if ((stanga < dim) && (heap[stanga] > heap[curent]))
                    deschimbat = stanga;
                if ((dreapta < dim) && (heap[dreapta] > heap[curent]))
                    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;
}