Pagini recente » Cod sursa (job #2738943) | Cod sursa (job #2279066) | Cod sursa (job #3004787) | Cod sursa (job #2122129) | Cod sursa (job #463392)
Cod sursa(job #463392)
#include <stdio.h>
#include <stdlib.h>
int N;
unsigned int H, U;
typedef struct s {
unsigned int h, m;
} gutuie;
struct HeapStruct {
int Capacity;
int Size;
gutuie* Elem;
};
typedef struct HeapStruct *Heap;
//definirea criteriului utilizat pentru sortarea gutuilor (descrescator dupa inaltime)
int compare (const void * a, const void * b) {
return ( ((*(gutuie*)b).h)/U - ((*(gutuie*)a).h)/U );
}
//definirea unor functii aplicate heap-ului
Heap initialize(int N) {
Heap H;
H = malloc(sizeof ( struct HeapStruct));
H->Elem = malloc((N + 1) * sizeof (gutuie));
H->Capacity = N;
H->Size = 0;
(H->Elem[0]).m = 32767;
return H;
}
void insert(gutuie X, Heap H) {
int i;
for (i = ++H->Size; (H->Elem[ i / 2 ]).m < X.m; i /= 2)
H->Elem[ i ] = H->Elem[ i / 2 ];
H->Elem[ i ] = X;
}
gutuie findMax(Heap H) {
return H->Elem[ 1 ];
}
gutuie deleteMax(Heap H) {
int i, Child;
gutuie MaxElement, LastElement;
MaxElement = H->Elem[ 1 ];
LastElement = H->Elem[ H->Size-- ];
for (i = 1; i * 2 <= H->Size; i = Child) {
Child = i * 2;
if (Child != H->Size && (H->Elem[ Child + 1 ]).m > (H->Elem[ Child ]).m)
Child++;
if (LastElement.m < (H->Elem[ Child ]).m)
H->Elem[ i ] = H->Elem[ Child ];
else
break;
}
H->Elem[ i ] = LastElement;
return MaxElement;
}
int isEmpty(Heap H) {
return H->Size == 0;
}
int max(int a, int b) {
if(a > b)
return a;
return b;
}
int main() {
FILE *fin = fopen("gutui.in","r");
FILE *fout = fopen("gutui.out","w");
//citirea datelor
fscanf(fin,"%d%u%u",&N,&H,&U);
gutuie* gutui = (gutuie*) malloc(N*sizeof(gutuie));
int i;
for(i = 0; i < N; i++)
fscanf(fin,"%u%u",&gutui[i].h,&gutui[i].m);
unsigned int quantity = 0;
//daca U = 0 problema este banala - se culeg toate gutuile
if(U == 0) {
for(i = 0; i < N; i++)
quantity += gutui[i].m;
fprintf(fout,"%u\n",quantity);
return 0;
}
//sortarea gutuilor, descrescator, dupa inaltime
qsort (gutui, N, sizeof(gutuie), compare);
//daca H nu se divide cu U, se determina inaltimea de start
int dif = U - H % U;
unsigned int top;
if (dif == U)
dif = 0;
int offset = U-dif;
top = 0;
Heap heap = initialize(N);
int n = N-1;
while((!isEmpty(heap) || n >= 0) && top <= H) {
//se culege elementul cu masa maxima, aflat in heap
if(!isEmpty(heap)) {
quantity += (deleteMax(heap)).m;
//se incrementeaza inaltimea curenta
top += U;
}
else {
//se incrementeaza inaltimea curenta
if(offset) {
top += U * max(1, (gutui[n].h - top + offset) / U) - offset;
offset = 0;
}
else
top += U * max(1, (gutui[n].h - top) / U);
}
//se insereaza in heap toate gutuile aflate sub inaltimea curenta
while (n >= 0 && gutui[n].h <= top) {
insert(gutui[n],heap);
n--;
}
}
fprintf(fout,"%u\n",quantity);
fclose(fout);
return 0;
}