Pagini recente » Borderou de evaluare (job #1290951) | Diferente pentru problema/geometrie intre reviziile 4 si 47 | Istoria paginii utilizator/cristi_89 | Cod sursa (job #2166000) | Cod sursa (job #439254)
Cod sursa(job #439254)
#include<stdio.h>
// #include<conio.h>
int h[100000]; //inaltime
int g[100000]; //greutate
//gutu gutui[100000];
int oc[100000]; // are avlori 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,stanga;
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;
int cules=0;
i=0;
int ok=1;
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
//cules++;
}
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;
}