Cod sursa(job #438464)

Utilizator lucicanuAndrei-Lucian Croitoru lucicanu Data 10 aprilie 2010 19:47:04
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.6 kb
# include <stdio.h>
# include <stdlib.h>

# define MAXL 100000

typedef struct gut{
               int h;  //inaltime
               int v;  //valoare
               int p;  //pasul maxim la care poate fi culeasa gutuia
               }Gutuie;

int compare(const void* a, const void* b){   //functia de comaprare pentru qsort
    Gutuie *aa = (Gutuie*)a;
    Gutuie *bb = (Gutuie*)b;
    if (aa->p < bb->p)
       return -1;
    else
        if (aa->p > bb->p)
           return 1;
        else
            if (aa->v < bb->v)
               return 1;
            else
                return -1;
}

int main(){
    int n, H, U, i, j, sol[MAXL], nsol, pas, s, k, l;
    Gutuie g[MAXL];
    FILE *fin, *fout;
    fin=fopen("gutui.in","r");
    fout=fopen("gutui.out","w");
    
    fscanf(fin,"%d%d%d",&n, &H, &U);
    for (i=0;i<n;i++){
        fscanf(fin,"%d%d",&g[i].h,&g[i].v); //citesc informatiile referitoare la gutuie 
        g[i].p = (H - g[i].h)/U + 1;        //calculez pasul la care poate fi culeasa
    }
    
    qsort(g,n,sizeof(Gutuie),*compare); //sortez crescator dupa pas si descrescator dupa valoare

    nsol = 0;
    for (i=0;i<n;i++){
        if (i==0 || g[i].p != g[i-1].p){ //pasul urmator;
           pas = g[i].p;
           for (j=i;j<n && g[j].p == pas && j-i<pas;j++){//parcurg gutuile de la pasul curent(sunt in ordine descrescatoare;
               if (nsol<pas){ //daca pot sa adaug la solutie fara sa elimin gutui culese anterior:
                  //inserez pe g[j].v in vectorul sol a.i. sa ramana sortat descrescator;
                  for (k=0;k<nsol;k++)
                      if (sol[k]<g[j].v)
                         break;
                  for (l=nsol;l>k;l--)
                      sol[l] = sol[l-1];
                  sol[l] = g[j].v;
                  nsol++;
               }
               else{
                    if (g[j].v > sol[nsol-1]){ //daca cea mai slaba gutuie din solutie e mai slaba decat gutuia curenta:
                       //elimin ultimul element din sol si inserez pe g[j].v;
                       for (k=0;k<nsol;k++)
                       if (sol[k]<g[j].v)
                          break;
                       for (l=nsol;l>k;l--)
                           sol[l] = sol[l-1];
                       sol[l] = g[j].v;
                                         
                    }
               }
           }
        }
    }
    s = 0; //calculez suma si o scriu in fisier:
    for (i=0;i<nsol;i++){
        s+=sol[i];
    }
    fprintf(fout,"%d\n",s);   
    fclose(fin);
    fclose(fout);
    return 0;
}