Cod sursa(job #442425)

Utilizator radoooradu matei radooo Data 14 aprilie 2010 15:25:09
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.26 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct 
{
    int h,g;      //structura de gutui cu campurile h=inaltime, g=greutate
} gutuie;

int comp(const void *a,const void *b)   //functia de sortare descrescator dupa inalitme pentru quicksort
{
    gutuie *aa=(gutuie*)a;
    gutuie *bb=(gutuie*)b;
    return (*bb).h-(*aa).h;
}

int actualizeaza(int cules[], int n, gutuie c)
{
    int min=cules[0],i,im=0;
    for(i=1;i<n;i++)              //calculez minimul din vectorul de cules
        if(min>cules[i])
        {
            min=cules[i]; 
            im=i;
        }
    if(c.g>min)                   //daca gutuia curenta e mai grea decat greutatea minima din vectorul de cules,
        cules[im]=c.g;            //o inlocuiesc cu cea curenta
    return min;
}

int main()
{
  int i,j=0,n,hmax,u,suma=0,m=-1,k=0;
  FILE* fin=fopen("gutui.in","rt");
  FILE* fout=fopen("gutui.out","wt");
  gutuie c;             
  fscanf(fin,"%i %i %i",&n,&hmax,&u);
  gutuie vg[n];                    //vg=vectorul de gutui
  for(i=0;i<n;i++)
      fscanf(fin,"%i %i",&vg[i].h,&vg[i].g);
  int cules[n];                    //cules=vectorul in care o sa pun greutatile gutuilor culese
  qsort(vg,n,sizeof(gutuie),comp); //sortarea dupa inaltime a vectorului de gutui
  for(i=0;i<n;i++)
  {    
      c=vg[i];                     //iau fiecare gutuie din vector
      if(c.h<=hmax)                //verific daca in momentul de fata se poate lua
      {
          cules[j]=c.g;            //daca da, ii pun greutatea in vectorul de cules 
          j++;                     //cresc indicele in vectorul de cules
          hmax=hmax-u;             //si cresc inaltimea crengilor prin scaderea lui hmax
          m=-1;
      }
      else                         //daca nu se mai poate lua in momentul de fata
          if(c.g>m)
              m=actualizeaza(cules,j,c); //daca are greutatea mai mare ca vreo gutuie deja culeasa, o culeg pe aceasta si renunt la gutuia mai usoara
 /* printf("m=%i\n",m);
  for(k=0;k<j;k++)
  printf("%i ",cules[k]);
  printf("\n");*/
  }
  for(i=0;i<j;i++)
      suma=suma+cules[i];            //suma gutuilor culese -> rezultatul cautat
  fprintf(fout,"%i\n",suma);
  fclose(fin);
  fclose(fout);
//  getch();
  return 0;
}