Cod sursa(job #439024)

Utilizator points_hunterAdrian Dobrescu points_hunter Data 11 aprilie 2010 11:50:28
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 2.88 kb
  #include<stdio.h>
 // #include<conio.h>

  struct gutu {
         int h;   //inaltime
         int g;   //greutate
         int p;   //prioritate
         };
 gutu gutui[100000];      
     int oc[100000];    // are avlori 0/1; daca prioritatea a fost data =1  
    
    void quickSortG(gutu vect[], int stanga, int dreapta) {  
       int i = stanga, j = dreapta;  
          gutu tmp;  
          int pivot = vect[stanga ].g;  
          while (i <= j) {  
                while (vect[i].g > pivot)  
                      i++;  
                while (vect[j].g < pivot)  
                      j--;  
               if (i <= j) {  
                     tmp = vect[i];  
                     vect[i] =vect[j];  
                     vect[j] = tmp;  
                     i++;  
                     j--;  
               }  
          
         };  
         if (stanga < j)  
               quickSortG(vect, stanga, j);  
         if (i < dreapta)  
              quickSortG(vect, i, dreapta);  
   }   
    
   int main(){
       
    FILE *f,*g;
    int N, H, U, i, auxh,max=0,k,s=0,stanga;
    f = fopen( "gutui.in", "r" );
    g = fopen( "gutui.out", "w" );
    fscanf(f, "%d", &N);
    fscanf(f, "%d", &H);
    fscanf(f, "%d", &U);
    
     for( i = 0; i < N; i ++){       
           fscanf ( f, "%d", &auxh );     //citim ialtimea
          gutui[i].h = (H-auxh)/U+1;     // pe ce nivel se afla gutuia
          if(gutui[i].h > max)           //nivelul maxim 
             max=gutui[i].h;               
        
          fscanf ( f, "%d", &gutui[i].g ); //citim greutatea
     
          }

    quickSortG(gutui,0,N-1);          //sortam dupa greutate
  
  int ind,j;
  int cules=0;
   i=0;
  int ok=1;
   while(i<N){                      //parcurgem gutuile in ordinea greutatii,pana cand prioritatea ajunge 0
            
              if(oc[gutui[i].h]==0 ){
                                oc[gutui[i].h]=1;       //alocam prioritatea     
                                s=s+gutui[i].g;         //gutuia este culeasa
                                cules++;
                                }
                                else { ind=gutui[i].h;  //vrem sa acordam prima prioritate disponibila
                                     while(oc[ind]!=0 && ind>0 )  
                                        ind--;           //prioritatea va fi mai mica decat cea gutui[i].h
                                        if(ind>0){       //daca s-a gasit o prioritate disponibila, o alocam
                                        oc[ind]=1;
                                        s=s+gutui[i].g;}  //culegem gutuia
                                        }                                
                                i++;                   
  }
  
fprintf(g,"%d",s);        
       //  getch();
         return 0; 
     
             
    
}