Pagini recente » Cod sursa (job #3219639) | Cod sursa (job #2348112) | Cod sursa (job #798760) | Cod sursa (job #2837761) | Cod sursa (job #438246)
Cod sursa(job #438246)
Utilizator |
alex copot |
Data |
10 aprilie 2010 16:38:34 |
Problema |
Gutui |
Scor |
100 |
Compilator |
c |
Status |
done |
Runda |
teme_upb |
Marime |
2.25 kb |
#include <stdio.h>
#include <stdlib.h>
// structuri de date folosite
// pentru reprezentarea gutuilor si a heapului binar
typedef struct {
long h;
long g;
} gutuie;
typedef struct {
long *a;
long n;
} heap;
gutuie *vg;
long N, H, U;
heap h;
void citeste()
{
FILE *f = fopen("gutui.in", "rt");
int i;
if ( f == NULL )
return;
fscanf(f, "%ld%ld%ld", &N, &H, &U);
vg = (gutuie*)calloc(sizeof(gutuie), N);
h.a = (long*)calloc(sizeof(long), N);
for (i = 0; i < N; i++) {
fscanf(f, "%ld%ld", &vg[i].h, &vg[i].g);
}
fclose(f);
}
// intoarce pasul la care gutuia 'gut' s-ar pierde daca nu ar fi culeasa
int pas(gutuie gut)
{
return (H - gut.h) / U + 1;
}
// functia de comparare pentru qsort
// gutuile sunt sortate crescator dupa pasul la care se pierd
int comp(const void *s1, const void *s2)
{
return ( H - ((gutuie*)s1)->h ) / U - ( H - ((gutuie*)s2)->h ) / U;
}
// functii pentru implementarea heapului
void swap(heap *h, int i, int j)
{
int tmp = h->a[i];
h->a[i] = h->a[j];
h->a[j] = tmp;
}
void addHeap(heap *h, int x)
{
int i;
h->n++;
i = h->n;
h->a[i] = x;
while (i > 1 && h->a[i/2]<x) {
swap(h, i, i/2);
i = i / 2;
}
}
// indicele valorii maxime dintre radacina i si copii stang si drept
inline int indmax(heap *h, int i)
{
int st, dr, m;
st = 2*i;
dr = 2*i + 1;
if ( st <= h->n && h->a[st] > h->a[i] )
m = st;
else
m = i;
if ( dr <= h->n && h->a[dr] > h->a[m])
m = dr;
return m;
}
// refacere heap dupa extragere element maxim
void heapify(heap *h, int i)
{
int im;
while (i <= h->n) {
im = indmax(h, i);
if (i == im)
break;
swap(h, i, im);
i = im;
}
}
int delHeap(heap *h)
{
int hmax;
if ( h->n < 1 )
return 0;
hmax = h->a[1];
h->a[1] = h->a[h->n];
h->n--;
heapify(h, 1);
return hmax;
}
int main(int argc, char **argv)
{
long sol, maxg, nci, ncmax, i;
citeste();
qsort(vg, N, sizeof(gutuie), comp);
ncmax = pas(vg[N-1]);
i = N - 1;
h.n = 0;
sol = 0;
for (nci = ncmax; nci >= 1 && i >= 0; nci--) {
while ( pas(vg[i]) == nci && i >= 0) {
addHeap(&h, vg[i].g);
i--;
}
maxg = delHeap(&h);
sol += maxg;
}
while ( h.n > 0 && nci >= 1 ) {
maxg = delHeap(&h);
sol += maxg;
nci--;
}
FILE *f = fopen("gutui.out", "wt");
fprintf(f, "%ld\n", sol);
fclose(f);
return 0;
}