Pagini recente » Cod sursa (job #723266) | Cod sursa (job #1779666) | Cod sursa (job #456646) | Cod sursa (job #2962159) | Cod sursa (job #460950)
Cod sursa(job #460950)
#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, nivel=0, total=0, heap[100001], dim=0, 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 poate gigel culege inainte
}
fclose (f);
qsort(gt, n, sizeof(gutui), compare);
//sortam crescator in fct de "etaj" si descrescator in fct de greutate
if (gt[0].inainte == 0)
{
fprintf(g, "%u", gt[0].greu);
fclose(g);
return 0;
}
nivel = gt[0].inainte;
total = gt[0].greu;
heap[0] = 0;
for (i=1; i<n; i++)
{
//introducem in heap
dim++;
heap[dim] = gt[i].greu;
//urcam elementul daca e cazul
unsigned curent = dim;
while ((heap[curent] > heap[(curent / 2)]) && (curent > 1))
{
//interschimbam cu parintele
aux = heap[curent / 2];
heap[curent / 2] = heap[curent];
heap[curent] = aux;
curent = curent / 2;
}
while (gt[i].inainte < nivel && (dim > 0))
{
nivel--;
//scoatem greutatea din varf
total += heap[1];
//si punem in locul ei cea mai din dreapta greutate de pe ultimul nivel
heap[1] = heap[dim];
dim--;
//coboram greutatea din varf
int ok = 1;
unsigned int curent = 1;
while (ok)
{
//verificam daca trebuie inlocuit cu fiul din stanga sau dreapta
unsigned int deschimbat = curent;
unsigned int stanga = 2 * curent;
unsigned int dreapta = 2 * curent + 1;
if ((stanga <= dim) && (heap[stanga] > heap[curent]))
deschimbat = stanga;
if ((dreapta <= dim) && (heap[dreapta] > heap[deschimbat]))
deschimbat = dreapta;
if (deschimbat != curent)
{
aux = heap[curent];
heap[curent] = heap[deschimbat];
heap[deschimbat] = aux;
curent = deschimbat;
}
else
ok = 0;
}
if (nivel == 0)
break;
}
nivel = gt[i].inainte;
}
while (nivel > 0 && dim > 0)
{
nivel--;
total += heap[1];
heap[1] = heap[dim];
dim--;
int ok = 1;
unsigned int curent = 1;
while (ok)
{
unsigned int deschimbat = curent;
unsigned int stanga = 2 * curent;
unsigned int dreapta = 2 * curent + 1;
if ((stanga <= dim) && (heap[stanga] > heap[curent]))
deschimbat = stanga;
if ((dreapta <= dim) && (heap[dreapta] > heap[deschimbat]))
deschimbat = dreapta;
if (deschimbat != curent)
{
aux = heap[curent];
heap[curent] = heap[deschimbat];
heap[deschimbat] = aux;
curent = deschimbat;
}
else
ok = 0;
}
}
fprintf(g, "%u", total);
fclose(g);
return 0;
}