Pagini recente » Cod sursa (job #686092) | Cod sursa (job #1539236) | Cod sursa (job #116061) | Cod sursa (job #439328) | Cod sursa (job #441073)
Cod sursa(job #441073)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <sstream>
#include <string>
#include <map>
using namespace std;
typedef pair <int, int> Int_Pair;
int main()
{
//salvez perechile inaltime - greutate intr-un multimap
//pt a evita problema sortarii dupa inaltime
multimap<int, int > gutui;
multimap<int, int>::iterator it;
multimap<int, int > rez;
FILE *in,*out;
in=fopen( "gutui.in","r" );
out=fopen( "gutui.out","w" );
int i=0, j=0, x=0, k=0, y=0, max=0;;
int N, H, U;
//citire N H U
fscanf(in,"%d %d %d",&N,&H,&U);
//citire si adaugare la multimap a perechilor inaltime- greutate din fisier
for(i=0;i<N;i++)
{
fscanf(in,"\n%d %d",&y,&x);
gutui.insert ( Int_Pair ( y , x ) );
}
int adaugat=0;
for (it = gutui.begin();it != gutui.end();it++)
{
//daca inaltimea la care este gutuia este mai mica decat inalmimea maxima
//la care poate ajunge gigel se culege
if ( it->first <=H )
{
//se adauga intr-un nou multimap (rez) si se scade din inaltimea
//la care se poate ajunge inaltimea U (cu cat se ridica crengile dupa
//fiecare gutuie culeasa)
rez.insert( Int_Pair ( it->second, it->first ) );
H=H-U;
}
else
{
//daca exista gutui culese si daca gutuia nu poate fi culeasa
//se verifica daca exista o gutuie deja culeasa cu greutatea mai
//mica decat a ei si se inlocuieste daca da
if (!rez.empty())
if ( it->second >= (rez.begin())->first )
{
//avand in vedere ca rez este deja sortat se sterge gutuia
//usoara si se inlocuieste cu cea aleasa
rez.erase(rez.begin());
rez.insert( Int_Pair ( it->second, it->first ) );
}
}
}
//se calculeaza greutatea tuturor gutuilor culese
for (it = rez.begin();it != rez.end();it++)
{
max += it->first;
}
fprintf(out,"%d",max);
fclose(in);
fclose(out);
return 0;
}