Pagini recente » Cod sursa (job #2801072) | Cod sursa (job #2038708) | Cod sursa (job #1131815) | Cod sursa (job #2055654) | Cod sursa (job #463386)
Cod sursa(job #463386)
// Popescu Maria, 324CA
#include <stdio.h>
#include <stdlib.h>
typedef struct { int h, c; } Gutuie;
int n, H, U;
Gutuie G[100021]; //G[i] este gutuia i data prin inaltime si greutate
int timp[100021]; //timp[i] este numarul maxim de gutui care pot fi culese inainte
int raspuns = 0; //raspuns este raspunsul final
int *heap, heap_sz; //structura de maxim-heap
//voi sorta gutuile crescator dupa inaltime
int cmp(const void *a, const void *b)
{
return ((Gutuie *)a)->h - ((Gutuie *)b)->h;
}
//citesc datele
void citeste()
{
int i;
FILE *f = fopen("gutui.in", "r");
fscanf(f, "%d %d %d", &n, &H, &U);
for (i = 1; i <= n; i++)
fscanf(f, "%d %d", &G[i].h, &G[i].c);
fclose(f);
}
//functie de interschimbare a doua elemente
void schimba(int *a, int *b)
{
int aux = *a;
*a = *b;
*b = aux;
}
//urc in heap o valoare inspre radacina
void urca(int *heap, int poz)
{
while (poz > 1)
{
if (heap[poz/2] < heap[poz])
{
schimba(heap+(poz/2), heap+poz);
poz /= 2;
}
else
break;
}
}
//interschimb un nod cu fiul maxim pana cand nodul ajunge mai mare decat ambii fii
void coboara(int *heap, int heap_size, int poz)
{
while (poz * 2 <= heap_size)
{
int mn = poz * 2;
if (poz * 2 + 1 <= heap_size && heap[poz * 2] < heap[poz * 2 + 1])
mn = poz * 2 + 1;
if (heap[mn] > heap[poz])
{
schimba(heap+mn, heap+poz);
poz = mn;
}
else
break;
}
}
//inserez o valoare in heap
void insereaza_in_heap(int *heap, int *heap_size, int val)
{
(*heap_size)++;
heap[*heap_size] = val;
urca(heap, *heap_size);
}
//sterg maximul(radacina) si returnez acest maxim
int afla_max_si_sterge(int *heap, int *heap_size)
{
if (heap_size == 0)
return 0;
int max = heap[1];
heap[1] = heap[*heap_size];
heap[*heap_size] = 0;
(*heap_size)--;
coboara(heap, *heap_size, 1);
return max;
}
void rezolva()
{
//sortez gutuile crescator dupa inaltime
qsort(G+1, n, sizeof(Gutuie), cmp);
int i, j, t, max_gutui;
for (i = 1; i <= n; i++)
timp[i] = (H-G[i].h)/U + 1;
heap = (int *)malloc(sizeof(int) * (n+1));
heap_sz = 0;
for (i = 1; i <= n; i++)
{
//daca nu mai pot culege gutuia, termin
if (G[i].h > H)
break;
j = i; t = timp[i];
while (timp[j] == t)
{
//inserez gutuia in heap si trec la urmatoarea
insereaza_in_heap(heap, &heap_sz, G[j].c);
++j;
}
//cate gutui am timp sa culeg
max_gutui = timp[i]-timp[j];
while (max_gutui > 0 && heap_sz > 0)
{
raspuns += afla_max_si_sterge(heap, &heap_sz);
--max_gutui;
}
i = j-1;
}
}
//afisez raspunsul
void scrie()
{
FILE *f = fopen("gutui.out", "w");
fprintf(f, "%d\n", raspuns);
fclose(f);
}
int main()
{
citeste();
rezolva();
scrie();
return 0;
}