Cod sursa(job #439273)

Utilizator cristinam.tanaseTanase Cristina cristinam.tanase Data 11 aprilie 2010 14:56:33
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 3.04 kb
  #include<stdio.h>
 // #include<conio.h>
      
     int h[100000];   //inaltime
     int g[100000];   //greutate
         
     int oc[100000];    // are valori 0/1; daca prioritatea a fost data =1  
    
    void quickSortG(int vect[], int stanga, int dreapta) {  
       int i = stanga, j = dreapta;  
          int tmp1,tmp2; 
          int pivot = vect[stanga ];  
          while (i <= j) {  
                while ( vect[i] > pivot )  
                      i ++;  
                while ( vect[j] < pivot )  
                      j --;  
               if (i <= j) {  
                     tmp1 = vect[i];
                     tmp2 = h[i];  
                     vect[i] = vect[j];
                     h[i] = h[j];  
                     vect[j] = tmp1;
                     h[j] = tmp2;  
                     i ++;  
                     j --;  
               }  
          
         };  
         if ( stanga < j )  
               quickSortG( vect, stanga, j);  
         if ( i < dreapta )  
              quickSortG( vect, i, dreapta );  
   }   
    
   int main(){
       
    FILE *f,*f1;
    int N, H, U, i, auxh, max=0,k, s=0;
    f = fopen( "gutui.in", "r" );
    f1 = 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
          h[i] = (H-auxh)/U+1;            // pe ce nivel se afla gutuia
          if(h[i] > max)                  //nivelul maxim 
             max=h[i];               
        
          fscanf ( f, "%d", &g[i] );      //citim greutatea
     
          }

    quickSortG(g,0,N-1);                  //sortam dupa greutate
  
  int ind,j;
  i=0;
  
   while(i<N ){                             //parcurgem gutuile in ordinea greutatii,pana cand prioritatea ajunge 0
            
              if(oc[h[i]]==0 ){
                                oc[h[i]]=1;       //alocam prioritatea     
                                s=s+g[i];         //gutuia este culeasa                      
                                }
                                else { 
                                     ind=h[i];  //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+g[i];
                                            }       //culegem gutuia
                                       
                                        } 
                                                                       
                                i++;                   
  }
  
fprintf(f1,"%d",s);        
       //  getch();
         return 0; 
     
             
    
}