Pagini recente » Monitorul de evaluare | Profil ilinca_stefi | Statistici Stoica Eva (evastoica) | Cod sursa (job #438747)
Cod sursa(job #438747)
#include <stdlib.h>
#include <stdio.h>
typedef struct {
int w;//greutate
int h;//inaltime
int t;//momentul maxim la care se poate culege gutuia
}gutuie;
typedef struct {//structura de maxheap
int *cont;
int dim;
}maxheap ;
void insert ( maxheap * h, int x){//functia de inserare (clasica) pentru maxheap reprezentat ca vector
int poz =++h->dim;
for( ; poz > 1 && x > h->cont[ poz / 2 ]; poz/= 2)
h->cont[poz] = h->cont[poz/2];
h->cont[poz] = x;
}
int compare (const void * elem1, const void * elem2){//pentru sortare
gutuie * e1=(gutuie *)elem1;
gutuie * e2=(gutuie *)elem2;
return (-e1->t + e2->t);
}
void swap (maxheap & h, int i, int j){
int t;
t=h.cont[i];
h.cont[i]=h.cont[j];
h.cont[j]=t;
}
void heapify (maxheap& h, int i) {//pentru del
int st, dr,m;
int aux;
st=2*i;
dr=st+1;
if (st<=h.dim && h.cont[st]>h.cont[i])
m=st;
else m=i;
if (dr<=h.dim && h.cont[dr]>h.cont[m])
m=dr;
if (m!=i){
swap (h,i,m);
heapify(h,m);
}
}
int del (maxheap & h) {
int hmax;
if (h.dim<=0) return -1;
hmax= h.cont[1];
h.cont[1]=h.cont[h.dim];
h.dim --;
heapify (h,1);
return hmax;
}
int main(){
int N,H,U;
FILE * f=fopen("gutui.in","r");
fscanf(f,"%d %d %d\n", &N,&H,&U);
gutuie gutui[N];//vector de "gutui"
int i,j;
for (i=0;i<N;i++)
fscanf(f, "%d %d\n", &(gutui[i].h),&(gutui[i].w));//citim greutatile si inaltimile
//calculam pentru fiecare gutuie, momentul de timp maxim (t) la care se poate culege
for (i=0;i<N;i++) {
if (gutui[i].h<=H) gutui[i].t=(H-gutui[i].h)/U+1;
else (gutui[i].t=-1);
}
//algoritmul alege gutuia cea mai grea care se poate alege la fiecare moment de timp, incepand cu cel mai indepartat
//calculam maximul din vectorul t (sa stim cate momente de timp consideram)
int max=gutui[0].t;
for (i=1;i<N;i++) if (gutui[i].t>max) max =gutui[i].t;
qsort ( (void *)gutui,N, sizeof(gutuie), compare );//sortam vectorul cu gutui dupa t pentru a ne fi mai usor sa selectam gutuile care pot fi alese la fiecare pas
int cant=0;//cantitatea de fructe culeasa
maxheap choices;//heapul in care tinem solutiile posibile (gutuile ce pot fi alese) la feicare pas
choices.dim=0;//initializam heapul
choices.cont=(int *)malloc(N*sizeof(int));
j=0;
for (i=max;i>0;i--){//pentru fiecare moment de timp (pas)
while (gutui[j].t==i) {
insert (&choices,gutui[j].w);//
// printf("%d ", gutui[j].w);
j++;
}
if (choices.dim>=1) {cant+=choices.cont[1]; //alegem gutuia cu greutatea maxima
del(choices);
}
}
FILE * g=fopen("gutui.out", "w");
fprintf(g,"%d",cant);
fclose(g);
}