Pagini recente » Cod sursa (job #3240279) | Cod sursa (job #2463111) | Cod sursa (job #2081439) | Cod sursa (job #1908349) | Cod sursa (job #441897)
Cod sursa(job #441897)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int h, w;
} gutui;
struct HeapStruct {
int Capacity;
int Size;
gutui *Elements;
};
typedef struct HeapStruct *Heap;
int N,H,U;
Heap Initialize(int MaxElements) {
Heap H;
H = (Heap) malloc (sizeof(struct HeapStruct));
H->Elements = (gutui*) malloc ((MaxElements + 1) * sizeof(gutui));
H->Capacity = MaxElements;
H->Size = 0;
(H->Elements[0]).w = 30000;
return H;
}
void MakeEmpty(Heap H) {
H->Size = 0;
}
/* H->Element[ 0 ] is a sentinel */
int isEmpty(Heap H) {
return H->Size == 0;
}
int IsFull(Heap H) {
return H->Size == H->Capacity;
}
void Insert(gutui X, Heap H) {
int i;
for (i = ++H->Size; H->Elements[i/2].w < X.w; i /= 2)
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = X;
}
gutui DeleteMax(Heap H) {
int i, Child;
gutui 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]).w > (H->Elements[ Child ]).w)
Child++;
/* Percolate one level */
if (LastElement.w < (H->Elements[Child]).w)
H->Elements[ i ] = H->Elements[ Child ];
else
break;
}
H->Elements[ i ] = LastElement;
return MaxElement;
}
gutui 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, H->Elements[i].w);
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];
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).w;
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],hp);
last--;
}
}
fprintf(out,"%d",greutate_totala);
/*
while ((apples.size() or available_weights.size()) and top <= H) {
if (available_weights.size()) {
picked_weight += available_weights.front();
std::pop_heap(available_weights.begin(), available_weights.end());
available_weights.pop_back();
top += U;
}
else {
top += U * std::max(1, (apples.back().h - top) / U);
}
while (apples.size() and apples.back().h <= top) {
available_weights.push_back(apples.back().w);
std::push_heap(available_weights.begin(), available_weights.end());
apples.pop_back();
}
}
return picked_weight;
}
*/
fclose(in);
fclose(out);
Destroy(hp);
return 0;
}