Cod sursa(job #437741)
#include<stdio.h>
#include<stdlib.h>
//structura gutuie
typedef struct gut
{
int nivel;
int greutate;
int inaltime;
}gutui;
//fct de comparare pt qsort - sorteaza gutui in fct de nivel si greutate
int comparator(const void * a,const void *b)
{
gutui *aa=(gutui *)a;
gutui *bb=(gutui *)b;
if ((*aa).nivel != (*bb).nivel) return (*aa).nivel-(*bb).nivel;
return (*bb).greutate-(*aa).greutate;
}
//fct de comparare pt qsort - sorteaza gutui in fct de inaltime
int comparator2(const void * a,const void *b)
{
gutui *aa=(gutui *)a;
gutui *bb=(gutui *)b;
return (*bb).inaltime-(*aa).inaltime;
}
//fct intoarce pozitia pe care se gaseste minimul dintr-un vector
int poz_minim(int vector[], int n)
{
int i;
int poz = 0;
int min = vector[0];
for (i=0;i<n;i++)
{
if (vector[i] < min)
{
min = vector[i];
poz = i;
}
}
return poz;
}
int main()
{
FILE *f=NULL,*g=NULL;
int N,H,U,nr_niv;
int i,j,n,niv,pozitie,k;
int greutate_culeasa=0;
gutui *mat, *mat2;
//citesc datele de intrare si calculez nivelele pe care sunt asezate gutuile
f=fopen("gutui.in","rt");
g=fopen("gutui.out","wt");
fscanf (f,"%i%i%i",&N,&H,&U);
nr_niv=H/U;
if(H%U != 0) nr_niv++;
mat = (gutui*)malloc(N*sizeof(gutui));
for(i=0;i<N;i++)
{
fscanf(f,"%i%i",&(mat[i].inaltime),&(mat[i].greutate));
if (mat[i].inaltime > H ) mat[i].nivel = 0;
else mat[i].nivel = ((H-mat[i].inaltime) / U )+1;
}
//sortez gutuile in functie de nivel si greutate
//qsort(mat, N, sizeof(gutui), comparator);
//creez un nou vector de gutui doar cu cele la care gigel poate ajunge
//de pe un nivel i gigel poate culege maxim i gutui,
//le vom pastra pe primele cele mai grele de pe acel nivel
n=0;
i=0;
mat2 = (gutui*)malloc(N*sizeof(gutui));
/*while(i<N)
{
niv=mat[i].nivel;
j=0;
while ((niv == mat[i].nivel) && (i<N) && (j<niv))
{
mat2[n]=mat[i];
n++;
i++;
j++;
}
while ((mat[i].nivel == niv) && (i<N)) i++;
}
N=n;*/
//sortez dupa inaltime
qsort(mat, N, sizeof(gutui), comparator2);
//creez un vector cu greutatile gutuilor pe care le culeg
int greutati[N];
i=0;
niv=0;
for(j=0;j<N;j++)
{
if (mat[j].nivel>niv)
{
greutati[i]=mat[j].greutate;
i++;
niv++;
}
else
{
pozitie=poz_minim(greutati,i);
if(mat[j].greutate > greutati[pozitie]) greutati[pozitie] = mat[j].greutate;
}
}
n=i;
//scriu datele de iesire
for (i=0;i<n;i++)
greutate_culeasa += greutati[i];
fprintf(g,"%i",greutate_culeasa);
fclose(f);
fclose(g);
return 0;
}