Pagini recente » Cod sursa (job #503937) | Cod sursa (job #2782463) | Cod sursa (job #2222511) | Cod sursa (job #28725) | Cod sursa (job #439024)
Cod sursa(job #439024)
#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;
}