Pagini recente » Cod sursa (job #312409) | Cod sursa (job #1375083) | Cod sursa (job #1248186) | Cod sursa (job #1462841) | Cod sursa (job #439238)
Cod sursa(job #439238)
#include <stdio.h>
#include <stdlib.h>
typedef struct gutui{
int height;
int weight;
} gutui;
int cmpr_by_weight (const void *x, const void *y){ //Comparator folosit de qsort
struct gutui *X = (struct gutui *)x;
struct gutui *Y = (struct gutui *)y;
return (int)(Y->weight - X->weight); //pozitiv daca y mai mare ca x
}
int main(){
FILE *f_in, *f_out;
int N, H, U;
int i, j;
int mom; //momentul la care cel tarziu poate fi culeasa o gutuie
int finalWeight = 0;
gutui *tree;
gutui *basket;
f_in = fopen("gutui.in", "r");
f_out = fopen("gutui.out", "w");
//Citire
fscanf(f_in, "%d%d%d", &N, &H, &U);
tree = (gutui*)malloc(N*sizeof(gutui));
for (i = 0; i < N; i++){
fscanf(f_in, "%d%d", &tree[i].height, &tree[i].weight);
}
//Sortam descrescator vectorul de gutui dupa greutate
qsort(tree, N, sizeof(struct gutui), cmpr_by_weight);
basket = (gutui*)malloc((N+1)*sizeof(gutui));
for (i = 1; i <= N; i++){ //initializam cosul de gutui
//basket[i].height = 0;
basket[i].weight = 0;
}
for (i = 0; i < N; i++){
mom = ( H - tree[i].height )/U + 1; //formula pt a afla cand poate fi culeasa cel tarziu gutuia curenta(totodata si cea mai grea gutuie)
if (!basket[mom].weight){ //daca in momentul respectiv nu e culeasa nicio gutuie o culegem pe aceasta
basket[mom].weight = tree[i].weight;
//basket[mom].height = tree[i].height;
}
else{ //daca in momentul respectiv se culege alta gutuie cautam un moment anterior in care poate fi culeasa
for (j = mom; j >= 1; j--)
if(!basket[j].weight){ //daca nu exista gutuie culeasa
basket[j].weight = tree[i].weight; //o culegem
//basket[j].height = tree[i].height;
break;
}
}
}
for (i = 1; i <= N; i++) //calculam masa totala din cos
if (basket[i].weight)
finalWeight += basket[i].weight;
fprintf(f_out, "%d\n", finalWeight); //afisam masa totala
fclose(f_in);
fclose(f_out);
return 0;
}