Pagini recente » Cod sursa (job #964132) | Cod sursa (job #1816509) | Cod sursa (job #439506)
Cod sursa(job #439506)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define CHILD(node) ((node) * 2 + 1) //copilul din stanga
typedef struct gutuie {
unsigned int h;
unsigned int g;
} GUTUIE;
typedef GUTUIE (*comp)(const void*,const void*);
int cresc (const void * a, const void * b)
{
if ((*(GUTUIE*)a).h == (*(GUTUIE*)b).h)
return -((*(GUTUIE*)a).g - (*(GUTUIE*)b).g);
return ((*(GUTUIE*)a).h - (*(GUTUIE*)b).h);
}
unsigned int parent(unsigned int i){
if (i % 2 == 0) return (i/2 - 1);
else return i/2;
}
void insert(unsigned int g, unsigned int *heap, unsigned int i){
heap[i] = g;
unsigned int aux;
while ((i > 0) && (heap[i] < heap[parent(i)])) {
aux = heap[parent(i)];
heap[parent(i)] = heap[i];
heap[i] = aux;
i = parent(i);
}
}
void minheapify(unsigned int *heap, unsigned int i, unsigned int n){
while ( CHILD(i) < n){
unsigned int child = CHILD(i);
if (child + 1 < n && heap[child] > heap[child+1]) //alegem cel mai mic copil
child++;
if (heap[i] > heap[child]){ //mutam cel mai mic nod in radacina
unsigned int temp = heap[i];
heap[i] = heap[child];
heap[child] = temp;
}
++i;
}
}
int main(){
int N,i;
unsigned int H,U,level,sum,k,x;
GUTUIE *g;
FILE *f,*o;
f = fopen("gutui.in","r");
o = fopen("gutui.out","w");
fscanf(f,"%d",&N);
fscanf(f,"%d",&H);
fscanf(f,"%d",&U);
g = malloc(N * sizeof (GUTUIE));
for (i = 0;i < N;i++){
fscanf(f,"%d",&x);
if (H >= x)
g[i].h = (H-x)/U + 1; //cream nivelele in structura (sunt mai usor de utilizat decat inaltimile brute)
fscanf(f,"%d",&g[i].g);
}
qsort(g, N, sizeof(GUTUIE), cresc); //sortam structura crescator pe nivel si la nivele egale decrescator dupa greutate
//complexitate Theta(n*logn);
unsigned int * heap = (unsigned int *)calloc(N,sizeof(unsigned int));
level = 0; //nr maxim de gutui care poate fi cules la un nivel
sum = 0;
k = 0; //retinem in k nr de gutui din heap
for (i = 0; i < N; i++){
if (level < g[i].h) {//daca ajungem la un nivel nou
level = g[i].h; //il actualizam
insert(g[i].g, heap, k); //inseram gutuia de pe noul nivel in heap (Theta(logn))
k++; //actualizam nr de gutui din heap
sum += g[i].g; //o adunam la suma
}
else if (level == g[i].h){ //daca intalnim o gutuie pe acelasi nivel
if (k < level){ //daca in heap mai este loc pentru gutui
insert(g[i].g, heap, k); //inseram o gutuie in heap pe pozitia k (Theta(logn))
k++;
sum += g[i].g; // si adunam la suma
}
else { //daca am atins in heap nr maxim de gutui pentru un nivel
if (heap[0] < g[i].g) { //daca minimul din heap e mai mic decat greutatea gutuii actuale
sum = sum - heap[0] + g[i].g; //actualizam suma
heap[0] = g[i].g; //inseram in radacina si apoi coboram
minheapify(heap, 0, k); //(Theta(logn))
}
}
}
}
fprintf(o,"%d\n",sum);
fclose(f);
fclose(o);
return 0;
}