Pagini recente » Cod sursa (job #1002236) | Cod sursa (job #1576836) | Cod sursa (job #2056856) | Cod sursa (job #2913040) | Cod sursa (job #441505)
Cod sursa(job #441505)
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;
//Structura in care se vor pastra cate niveluri mai pot urca gutuile si masa lor
typedef struct {
int nivel;
int masa;
} Gutui;
//Functia ce contine criteriul de comparare pentru qsort
//Se sorteaza dupa nivel si dupa masa in cazul in care nivelurile sunt egale
int compare(const void *c, const void *d) {
const Gutui *a = (const Gutui *)c;
const Gutui *b = (const Gutui *)d;
if(a->nivel!=b->nivel)
return (a->nivel - b->nivel);
return(b->masa - a->masa);
}
int main() {
int h_max, nr_gutui, d_h;
int i, j, nr_puse=0;
Gutui *gut;
multimap <int, int > puse;
multimap <int, int>::iterator iter;
int strans=0;
FILE *in, *out;
in=fopen("gutui.in","r");
out=fopen("gutui.out","w");
fscanf(in,"%d ", &nr_gutui);
fscanf(in,"%d ", &h_max);
fscanf(in,"%d", &d_h);
gut=(Gutui *)malloc(nr_gutui*sizeof(Gutui));
for(i=0;i<nr_gutui;i++) {
//se citeste masa si inaltimea gutuilor si se calculeaza cate niveluri mai pot urca
fscanf(in,"\n%d %d",&j, &gut[i].masa);
gut[i].nivel=(h_max-j)/d_h+1;
}
//se sorteaza gutuile dupa inaltime si dupa masa
qsort(gut, nr_gutui, sizeof(Gutui), compare);
//pentru fiecare gutuie daca se poate ajunge la ea se adauga in multimap
for(i=0;i<nr_gutui;i++) {
if(gut[i].nivel-nr_puse>0) {
puse.insert( pair<int, int> (gut[i].masa, 0));
nr_puse++;
}
//daca s-a depasit nivelul la care se putea ajunge cu o unitate se verifica daca
//masa gutuii curente este mai mare decat cea mai mica din multiset se inlocuieste
//aceasta cu valoarea curenta
else
if(puse.size()>0)
if(gut[i].masa>(puse.begin())->first) {
puse.erase(puse.begin());
puse.insert( pair<int, int> ( gut[i].masa, 0));
}
}
//se parcurge multisetul pentru a calcula masa maxima
for(iter=puse.begin();iter!=puse.end();iter++)
strans+=iter->first;
fprintf(out,"%d",strans);
fclose(in);
fclose(out);
return 0;
}