Pagini recente » Cod sursa (job #3128307) | Cod sursa (job #381978) | Cod sursa (job #2300289) | Cod sursa (job #1818865) | Cod sursa (job #436771)
Cod sursa(job #436771)
#include <stdlib.h>
#include <stdio.h>
typedef struct {
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;
}
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) {
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);
int w[N],h[N];//vectori cu greutatile si inaltimile gutuilor
int i,j;
for (i=0;i<N;i++)
fscanf(f, "%d %d\n", &h[i],&w[i]);
//calculam pentru fiecare gutuie, momentul de timp maxim (t) la care se poate culege
int t[N];
for (i=0;i<N;i++) {
t[i]=(H-h[i])/U+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=t[0];
for (i=1;i<N;i++) if (t[i]>max) max =t[i];
maxheap heap[max];// un vector de heapuri (pentru fiecare moment de timp), primul element al heapului corespunzator
//va contine gutuia cu greutate maxima (am folosit maxheap pentru a mari viteza aflarii celui mai mare element
for (j=0;j<max;j++){
heap[j].dim=0;//initializam heapul
heap[j].cont=(int *)malloc(45*sizeof(int));
}
for (i=0;i<N;i++) //pentru fiecare gutuie
insert(&heap[t[i]-1],w[i]);//adaugam greutatea gutuii in heapul corespunzator momentului de timp t[i]
int aux=0;//calculam cate heap-uri sunt vide
int cant=0;//cantitatea de fructe culeasa
for (i=max-1;i>0;i--){
if (heap[i].dim>=1) cant=cant+heap[i].cont[1];// se culege gutuia si se adauga greutatea ei
else aux++; //se incrementeaza numarul de alegeri care va ramane
for (j=2;j<=heap[i].dim;j++) insert (&heap[i-1],heap[i].cont[j]);
}
// for (j=1;j<=heap[0].dim;j++) printf("%d ", heap[0].cont[j]);
// printf("\n");
for (j=1;j<=aux+1;j++){ //pentru cate alegeri mai avem (aux +1)
//alegem din primul heap (corespunzator celui mai apropiat moment de timp)
cant=cant+heap[0].cont[1];
del(heap[0]);
// for (j=1;j<=heap[0].dim;j++) printf("%d ", heap[0].cont[j]);
// printf("\n");
}
// getchar();
FILE * g=fopen("gutui.out", "w");
fprintf(g,"%d",cant);
fclose(g);
}