Cod sursa(job #438930)

Utilizator adriana.erbaruAdriana Erbaru adriana.erbaru Data 11 aprilie 2010 04:22:44
Problema Gutui Scor 40
Compilator cpp Status done
Runda teme_upb Marime 1.97 kb
#include <stdio.h>
#include <stdlib.h>

struct fructa
{
    long i, h, g, n;
};

int cmpN(const void * p, const void * q)  // (a,a1) <? (b,b1)
{
    fructa x = *(fructa*)p;
    fructa y = *(fructa*)q;
    return (x.n-y.n);
}

int cmpG(const void * p, const void * q)  // (a,a1) <? (b,b1)
{
    fructa x = *(fructa*)p;
    fructa y = *(fructa*)q;
    return (x.g-y.g);
}

int main()
{
    fructa f[100000], g[100000];
    long H, N, U;
    long i;
    
    FILE *fin, *fout;
    fin = fopen("gutui.in", "r");
    fout = fopen("gutui.out", "w");
    
    
    long nSol = 0;
    long gSol = 0;
    long sol[100000];
    
    fscanf(fin, "%d%d%d", &N, &H, &U);
       
    for (i=0; i<N; i++)
    {
        fscanf(fin, "%d%d", &f[i].h, &f[i].g);
        f[i].n = (H-f[i].h) / U;
        if (f[i].n==0)
        {
            i=i-1;
            N=N-1;
        }
    }
    
    /* qsort(f, N, sizeof(fructa), cmpG);
    
    for (i=0; i<N; i++)
        {
            f[i].i = i;
        }
    
    g = f; */
    
    qsort(f, N, sizeof(fructa), cmpN);
    
    int k;
    
    int minSol;
    
    for (k=0; k<N; k++)
    {
        // |S_(k-1)| = nSol
        if (f[k].n >= nSol ) // n_k >= |S_(k-1)|
        {
            sol[nSol] = k;
            nSol++;
            gSol += f[k].g;
        }
        else // n_k < |S_(k-1)|
        {
            // in acest caz n_k + 1 = nSol
            // cautam minimul in solutie
            minSol = 0;
            for (i=0; i<nSol; i++)
            {
                if ( f[sol[i]].g < f[sol[minSol]].g )
                {
                    minSol = i;
                }
            }
            if ( f[sol[minSol]].g < f[k].g )
            {
                gSol = gSol + f[k].g - f[sol[minSol]].g;
                sol[minSol]=k;
            }
        }
    }                  
      
    fprintf(fout, "%d", gSol);
    
    fclose(fin);
    fclose(fout);

    return 0;
}