Pagini recente » Cod sursa (job #2720697) | Cod sursa (job #88117) | Cod sursa (job #1490970) | Cod sursa (job #638472) | Cod sursa (job #442504)
Cod sursa(job #442504)
#include <stdio.h>
#include <stdlib.h>
typedef struct g
{
unsigned int inainte;
unsigned int greu;
}gutui;
int compare (const void *x, const void *y)
{
if ((*(gutui*)x).inainte == (*(gutui*)y).inainte)
return -((*(gutui*)x).greu - (*(gutui*)y).greu);
else
return -((*(gutui*)x).inainte - (*(gutui*)y).inainte);
}
int main()
{
FILE *f, *g;
f = fopen ("gutui.in", "r");
g = fopen ("gutui.out", "w");
unsigned int n, h, u, i, max=0, nivel=0, total=0, heap[100001], dim=1, aux;
fscanf (f, "%u", &n);
fscanf (f, "%u", &h);
fscanf (f, "%u", &u);
gutui gt[n];
for (i=0; i<n; i++)
{
fscanf (f, "%u", >[i].inainte);
fscanf (f, "%u", >[i].greu);
gt[i].inainte = (h - gt[i].inainte) / u; //cate gutui putem culege inaintea ei
if (gt[i].inainte > max)
max = gt[i].inainte;
}
fclose (f);
//in n citim, in n log n sortam, in n log n construim heapu
qsort(gt, n, sizeof(gutui), compare);
//for (i=0; i<n; i++)
// printf("%u %u\n", gt[i].inainte, gt[i].greu);
for (i=0; i<n; i++)
{
//introduc in heap
heap[dim-1] = gt[i].greu;
//urc daca e cazul
while ((dim > 1) && (heap[dim - 1] > heap[(dim - 2) / 2]))
{
//interschimb cu parintele
aux = heap[(dim - 2) / 2];
heap[(dim - 2) / 2] = heap[dim - 1];
heap[dim - 1] = aux;
}
dim++;
//printf ("%u\n", i);
if (gt[i+1].inainte < gt[i].inainte) //daca am terminat cu un nivel
{
nivel++;
//printf("gata nivelu %u\n", nivel);
//scot greutatea din varf
total += heap[0];
dim--;
//si pun in locul ei cea mai din dreapta greutate de pe ultimul nivel
heap[0] = heap[dim - 1];
//cobor greutatea din varf
int ok = 1;
unsigned int curent = 0;
while (ok)
{
unsigned int deschimbat = curent;
unsigned int stanga = 2 * curent + 1;
unsigned int dreapta = 2 * curent + 2;
if ((stanga < dim) && (heap[stanga] > heap[curent]))
deschimbat = stanga;
if ((dreapta < dim) && (heap[dreapta] > heap[curent]))
deschimbat = dreapta;
if (deschimbat != curent)
{
aux = heap[curent];
heap[curent] = heap[deschimbat];
heap[deschimbat] = aux;
curent = deschimbat;
}
else
ok = 0;
}
if (nivel == (max + 1))
break;
}
}
while (nivel < (max + 1) && (dim > 0))
{
nivel++;
//printf("gata nivelu %u\n", nivel);
//scot greutatea din varf
total += heap[0];
dim--;
//si pun in locul ei cea mai din dreapta greutate de pe ultimul nivel
heap[0] = heap[dim - 1];
//cobor greutatea din varf
int ok = 1;
unsigned int curent = 0;
while (ok)
{
unsigned int deschimbat = curent;
unsigned int stanga = 2 * curent + 1;
unsigned int dreapta = 2 * curent + 2;
if ((stanga < dim) && (heap[stanga] > heap[curent]))
deschimbat = stanga;
if ((dreapta < dim) && (heap[dreapta] > heap[curent]))
deschimbat = dreapta;
if (deschimbat != curent)
{
aux = heap[curent];
heap[curent] = heap[deschimbat];
heap[deschimbat] = aux;
curent = deschimbat;
}
else
ok = 0;
}
}
fprintf(g, "%lu", total);
fclose(g);
return 0;
}