Pagini recente » Cod sursa (job #837259) | Cod sursa (job #1224722) | Cod sursa (job #785688) | Cod sursa (job #1190481) | Cod sursa (job #442205)
Cod sursa(job #442205)
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
unsigned long int h,g; //structura de gutui cu campurile h=inaltime, g=greutate
} gutuie;
int comp(const void *a,const void *b) //functia de sortare descrescator dupa inalitme pentru quicksort
{
gutuie *aa=(gutuie*)a;
gutuie *bb=(gutuie*)b;
return (*bb).h-(*aa).h;
}
void actualizeaza(unsigned long int cules[], int n, gutuie c)
{
int min=cules[0],i,im=0;
for(i=1;i<n;i++) //calculez minimul din vectorul de cules
if(min>cules[i])
{
min=cules[i];
im=i;
}
// printf("%i %i\n",min,im);
if(c.g>min) //daca gutuia curenta e mai grea decat greutatea minima din vectorul de cules,
cules[im]=c.g; //o inlocuiesc cu cea curenta
}
int main()
{
unsigned long int hmax,u,suma=0;
int i,j=0,n;
FILE* fin=fopen("gutui.in","rt");
FILE* fout=fopen("gutui.out","wt");
gutuie c;
fscanf(fin,"%i",&n);
fscanf(fin,"%lu",&hmax);
fscanf(fin,"%lu",&u);
gutuie vg[n]; //vg=vectorul de gutui
for(i=0;i<n;i++)
fscanf(fin,"%lu %lu",&vg[i].h,&vg[i].g);
unsigned long int cules[n]; //cules=vectorul in care o sa pun greutatile gutuilor culese
qsort(vg,n,sizeof(gutuie),comp); //sortarea dupa inaltime a vectorului de gutui
for(i=0;i<n;i++)
{
c=vg[i]; //iau fiecare gutuie din vector
if(c.h<=hmax) //verific daca in momentul de fata se poate lua
{
cules[j]=c.g; //daca da, ii pun greutatea in vectorul de cules
j++; //cresc indicele in vectorul de cules
hmax=hmax-u; //si cresc inaltimea crengilor prin scaderea lui hmax
}
else //daca nu se mai poate lua in momentul de fata
actualizeaza(cules,j,c); //daca are greutatea mai mare ca vreo gutuie deja culeasa, o culeg pe aceasta si renunt la gutuia mai usoara
/* for(k=0;k<j;k++)
printf("%i ",cules[k]);
printf("\n");*/
}
for(i=0;i<j;i++)
suma=suma+cules[i]; //suma gutuilor culese -> rezultatul cautat
fprintf(fout,"%lu\n",suma);
/*for(i=0;i<n;i++)
printf("%lu\n",vg[i].h);*/
fclose(fin);
fclose(fout);
// getch();
return 0;
}