Pagini recente » Cod sursa (job #1801962) | Cod sursa (job #2610626) | Cod sursa (job #3177559) | Cod sursa (job #407011) | Cod sursa (job #440370)
Cod sursa(job #440370)
#include <fstream>
#include <stdlib.h>
using namespace std;
// gutuie
struct gutuie {
int g; // greutatea
int n; // nr max de gutui culese anterior pt care gutuia ramane accesibila, numit "nivel"
};
// nod de lista inlantuita
struct nod {
int val; // valoarea = greutatea gutuii
nod* next;
nod() {
next = NULL;
}
};
#define S (sizeof(gutuie))
// comparara dupa nivel - criteriu primar si dupa greutate, criteriu secundar
int cmp_n(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
int r = f1->n - f2->n;
return (r == 0 ? f1->g - f2->g : r);
}
int main() {
ifstream in ("gutui.in");
ofstream out("gutui.out");
int n, h, u, r = 0, nr = 0, ch, cg, cn, i, j;
gutuie *gutui;
nod **gn;
/***********************************************************************************************************
* - citire din fisier
* - o prima selectie - selectatrea cazurilor convenabile, adica
* eliminarea gutuilor la care nu se poate ajunge din prima , adica nivelul < 0 si
* a celor cu greutate nula (daca exista)
* - nr gutuilor ramase dupa aceasta prima selectie fiind nr <= n
*
***********************************************************************************************************/
in >> n >> h >> u;
gutui = new gutuie[n];
r = 0;
for (i = 0; i < n; i++) {
in >> ch >> cg; // citire inaltime si greutate
cn = (h - ch); // calcul nivel
if (cn >= 0 && cg > 0) { // se adauga numai cazurile convenabile
r += cg;
gutui[nr].g = cg;
gutui[nr].n = cn / u;
nr++;
}
}
n = nr;
if (n <= 1) {
out << r;
return 0;
}
qsort(gutui, n, S, cmp_n); // sortare dupa nivel O(n log n)
int maxn = gutui[n - 1].n + 1; // nr de niveluri
gn = new nod*[maxn]; // vector de liste inlantuite,
// qn[i] = inceputul unei liste cu gutuile de pe nivelul i, in ordinea descrescatoare a greutatii
/**********************************************************************************************************************************
*
* initial, consider ce se aleg gutuile care sunt capete de lista (cu greutatea ce mai mare) pe fiecare nivel
* insa o gutuie de pe un nivel superior unui nivel i, care nu este maxima pentru acel nivel (nu este cap de lista)
* poate inlocui o gutuie de pe nivelul i, daca are o greutate mai mare ca aceata
*
* voi face o parcurgere crescatoare a nivelurilor, incepand cu nivelul 1, facand unde este posibil aceste inlocuiri
*
**********************************************************************************************************************************/
for (i = 0; i < maxn; i++)
gn[i] = NULL;
j = 0; // nivelul curent
for (i = 0; i < n; i++) {
while (gutui[i].n != j)
j++;
nod* nn = new nod;
nn->val = gutui[i].g;
nn->next = gn[j];
gn[j] = nn;
}
int m, mi;
bool ok;
// pentru fiecare nivel, incepand cu 1
for (i = 1; i < maxn; i++) {
nod* nn = gn[i];
// daca exista mai mult de o gutuie pe nivelul i
if (nn == NULL || nn->next == NULL) {
continue;
}
nn = nn->next;
nr = 1;
again:
// se gaseste gutuia cu greutatea minima "m" de nivel < i, precum si indexul acesteia, "mi"
ok = false;
m = INT_MAX;
for (j = i - 1; j >= 0; j--) {
if (gn[j] == NULL) {
if (m != 0) {
m = 0;
mi = j;
}
}
else {
if (gn[j]->val < m) {
m = gn[j]->val;
mi = j;
}
}
}
// daca urmatoarea gutuie de pe nivelul i este mai grea decat minima, aceasta o va inlocui
if (nn->val > m) {
ok = true; // s-a facut inlocuire
if (m == 0)
gn[mi] = new nod;
gn[mi]->val = nn->val; // efectuare inlocuire
}
nr++; // creste nr gutui de pe nivelul i
nn = nn->next;
/******************************************************************************************************************************
*
* daca gutuia curenta a inlocuit gutuia cu greutate minima (altfel cu siguranta nici o alta gutuie de pe nivelul i
* ce urmeaza in lista, avand greutatea mai mica nu o va inlocui)si
* mai exitsta o gutuie pe nivelul i si
* nr de gutui de pe nivelul i care au inlocuit alte gutui <= i
* se mai incearca o inlocuire
*
*******************************************************************************************************************************/
if (nr <= i && nn != NULL && ok)
goto again;
}
// se aduna gutuile dupa efectuarea tuturor inlocuirilor
r = 0;
for (i = 0; i < maxn; i++)
r += ((gn[i] == NULL) ? 0 : gn[i]->val);
out << r;
return 0;
}