Pagini recente » Cod sursa (job #1947644) | Cod sursa (job #2649598) | Cod sursa (job #997978) | Cod sursa (job #2960713) | Cod sursa (job #442096)
Cod sursa(job #442096)
#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;
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] = 30000;
return H;
}
void MakeEmpty(Heap H) {
H->Size = 0;
}
/* H->Element[ 0 ] is a sentinel */
int isEmpty(Heap H) {
return H->Size == 0;
}
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;
}
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) {
/* Find smaller child */
Child = i * 2;
if (Child != H->Size && H->Elements[Child+1] > H->Elements[ Child ])
Child++;
/* Percolate one level */
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 compare (const void * a, const void * b) {
return ( ((*(gutui*)b).h)/U - ((*(gutui*)a).h)/U );
}
int max(int x, int y) {
return x>y?x:y;
}
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[N];
ElemType aux;
for (i=0; i<N; i++)
fscanf(in,"%d%d%c",&g[i].h,&g[i].w,&c);
qsort (g, N, sizeof(gutui), compare);
int greutate_totala = 0;
int offset = U - H % U;
if (offset == U) offset = 0;
int top = offset - U;
int last = N-1;
if (U == 0) {
for (i=0; i<N; i++)
greutate_totala += g[i].w;
fprintf(out,"%d\n",greutate_totala);
return 0;
}
Heap hp = Initialize(N);
while ( ( last >=0 || !isEmpty(hp) ) && top <= H) {
if (!isEmpty(hp)) {
greutate_totala += FindMax(hp);
aux = DeleteMax(hp);
top += U;
}
else {/*
if(offset) {
top += U * max(1, (g[last].h - top + offset) / U) - offset;
offset = 0;
}
else */
top += U * max(1, (g[last].h - top) / U);
}
while (last >=0 && g[last].h <= top) {
Insert(g[last].w,hp);
last--;
}
}
fprintf(out,"%d",greutate_totala);
fclose(in);
fclose(out);
Destroy(hp);
return 0;
}