Pagini recente » Cod sursa (job #2650313) | Cod sursa (job #2980774) | Cod sursa (job #2463107) | Cod sursa (job #1375901) | Cod sursa (job #442234)
Cod sursa(job #442234)
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct {
int h, w;
} gutui;
struct HeapStruct {
int Capacity;
int Size;
ElemType *Elements;
};
typedef struct HeapStruct *Heap;
int N,H,U;
//functii pentru implementarea unui heap
Heap Initialize(int MaxElements) {
Heap H;
H = (Heap) malloc (sizeof(struct HeapStruct));
H->Elements = (ElemType*) malloc ((MaxElements + 1) * sizeof(ElemType));
H->Capacity = MaxElements;
H->Size = 0;
H->Elements[0] = 3000000;
return H;
}
/* H->Element[ 0 ] is a sentinel */
int isEmpty(Heap H) {
return H->Size == 0;
}
//inserare in heap
void Insert(ElemType el, Heap H) {
int i;
for (i = ++H->Size; H->Elements[i/2] < el; i /= 2)
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = el;
}
//stergere din
ElemType DeleteMax(Heap H) {
int i, Child;
ElemType MaxElement, LastElement;
if (isEmpty(H))
return H->Elements[0];
MaxElement = H->Elements[1];
LastElement = H->Elements[H->Size--];
for (i = 1; i * 2 <= H->Size; i = Child) {
Child = i * 2;
if (Child != H->Size && H->Elements[Child+1] > H->Elements[ Child ])
Child++;
if (LastElement < H->Elements[Child])
H->Elements[i] = H->Elements[ Child ];
else
break;
}
H->Elements[i] = LastElement;
return MaxElement;
}
ElemType FindMax(Heap H) {
if (!isEmpty(H))
return H->Elements[1];
return H->Elements[0];
}
void Destroy(Heap H) {
free(H->Elements);
free(H);
}
void afisare(Heap H, FILE *out) {
int i;
for (i=0; i<H->Size; i++)
fprintf(out,"%d %d\n",H->Elements[i], H->Elements[i]);
fprintf(out,"\n");
}
int compareTo (const void * a, const void * b) {
if ( ((*(gutui*)b).h)/U > ((*(gutui*)a).h)/U )
return 1;
else if ( ((*(gutui*)b).h)/U < ((*(gutui*)a).h)/U )
return -1;
else
return 0;
}
int max(int x, int y) {
return x>y?x:y;
}
int max_w_n (gutui *g, int *first) {
int max = -1000000, i;
for (i=*first; i<N; i++)
if (g[i].h < H && g[i].h+U > H)
if (max < g[i].w)
max = g[i].w;
*first = i;
return max;
}
int main() {
int i;
char c;
FILE *in = fopen("gutui.in","r");
FILE *out = fopen("gutui.out","w");
fscanf(in,"%d%d%d%c",&N,&H,&U,&c);
gutui *g = (gutui*) malloc (N*sizeof(gutui));
ElemType aux;
for (i=0; i<N; i++) // citire date din fisier
fscanf(in,"%d%d%c",&g[i].h,&g[i].w,&c);
qsort (g, N, sizeof(gutui), compareTo); //sortarea vectorului de structuri de tip gutui in ordine descrescatoare a inaltimii gutuilor
//for (i=0; i<N; i++)
// fprintf(out,"%d %d\n",g[i].h,g[i].w);
//printf("%d\n",max_w_n(g));
long int greutate_totala = 0; //offset = pozitia curenta
int offset = U - H % U;
if (offset == U) offset = 0;
int top = offset - U;
int iter = 1;
/* int top, iter = 1;
if(H%U == 0)
top = U; //pozitia relativa pe ultimul nivel
else
top = H - ((H/U)*U);
*/
int last = N-1;
if (U == 0) { //daca toate gutuile sunt la aceeasi inaltime, se aduna toate
for (i=0; i<N; i++)
greutate_totala += g[i].w;
fprintf(out,"%ld\n",greutate_totala);
return 0;
}
Heap hp = Initialize(N); //initializare heap
while ( ( last >= 0 || hp->Size > 0 ) && top <= H) {
if (hp->Size > 0) { //daca exista elemente in heap-ul maxim
greutate_totala += FindMax(hp); // se adauga la greutatea totala valoarea maxima din heap
aux = DeleteMax(hp); //si se sterge acea valoare din heap
top += U; //creste pozitia curenta cu U
}
else if (iter == 0)
top += U;
iter = 0;
//top += U * max(1, (g[last].h - top) / U); //pozitia curenta devine inaltimea gutuiului celui mai de jos
while (last >= 0 && g[last].h <= top) {
//if (g[last].h > top) break;
Insert(g[last].w,hp);
last--;
}
}
fprintf(out,"%ld",greutate_totala);
fclose(in);
fclose(out);
Destroy(hp);
free(g);
return 0;
}