Pagini recente » Atasamentele paginii Profil Arnettse50x | Cod sursa (job #441368)
Cod sursa(job #441368)
#include<stdio.h>
#include<stdlib.h>
//structura unei gutui: inaltime si greutate
typedef struct{
int high;
int weight;
}gutuie;
int comparator(const void * g1,const void * g2){
if( (*(gutuie*)g1).high != (*(gutuie*)g2).high )
return ( (*(gutuie*)g1).high - (*(gutuie*)g2).high );
else
return ( (*(gutuie*)g1).weight - (*(gutuie*)g2).weight );
}
int compare (const void * a, const void * b){
return ( *(int*)a - *(int*)b );
}
int main(){
int i = 0, j = 0;
FILE* fd = fopen("gutui.in", "r");
int N,H,U;
//citire date de intrare
fscanf(fd, "%d", &N);
fscanf(fd, "%d", &H);
fscanf(fd, "%d", &U);
gutuie* gutui = NULL;
gutui = (gutuie *)malloc(N * sizeof(gutuie));
for( i = 0 ; i < N; i++){
fscanf(fd, "%d", &gutui[i].high);
fscanf(fd, "%d", &gutui[i].weight);
}
fclose(fd);
//sortare in functie de inaltimi
qsort(gutui, N, sizeof(gutuie), comparator);
//parcurgere pe nivele folosind un vector in care sunt pastrate toate
//greutatile gutuilor care se afla pe nivelul curent
//vectorul se modifica la fiecare pas de incrementare al nivelului,astfel
//se sorteaza, se scoate elementul maxim, care este adaugat la rezultatul final
//iar apoi se continua adaugarea greutatilor corespunzatoare nivelului urmator
int * heap = NULL;
heap = (int *)malloc(N * sizeof(int));//N e numarul maxim de gutui care pot fi pe un
//anumit nivel
for( i = 0; i < N; i++)
heap[i] = 0;
int sum_weight = 0; //rezultatul final = suma greutatilor gutuilor adunate;
int layer0 = (gutui[0].high / U) - (gutui[0].high % U == 0 ? 1 : 0); // nivelul de la care plecam(de jos in sus)
i = 0;j=0;
do{
for( ; (layer0 + 1) * U >= gutui[i].high; i++)
heap[j++] = gutui[i].weight;
qsort(heap, j, sizeof(int), compare);
sum_weight = sum_weight + heap[j - 1];
j = j - 1; //se decrementeaza deoarece se va inlocui elementul maxim, deja "cules"
layer0++;
}while( layer0 < H/U ); //a doua conditie e pentru cazul in care
FILE * g=fopen("gutui.out", "w");
fprintf(g,"%d",sum_weight);
fclose(g);
return 0;
}