Pagini recente » Cod sursa (job #1739972) | Cod sursa (job #1223970) | Cod sursa (job #1873995) | Cod sursa (job #1247553) | Cod sursa (job #440153)
Cod sursa(job #440153)
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <map>
using namespace std;
typedef pair <long, long> Int_Pair;
int main()
{
//salvez perechile inaltime - greutate intr-un multimap
//pt a evita problema sortarii dupa inaltime
multimap<long, long, std::greater<long> > gutui;
multimap<long, long>::iterator it;
multimap<long, long > rez;
ifstream in( "gutui.in" );
ofstream out( "gutui.out" );
string line;
long v[3];
long i=0, j=0, x=0, k=0, y=0, max=0;;
long N, H, U;
//citire N H U
getline (in, line);
string numar;
for (i=0; i<=line.size(); i++)
{
if (line[i] != ' ' ) numar.push_back( line[i] );
else
{
istringstream r( numar );
r>>x;
v[j] = x;
numar.clear();
j++;
}
}
istringstream r( numar );
r>>x;
v[j] = x;
numar.clear();
N = v[0];
H = v[1];
U = v[2];
//citire si adaugare la multimap a perechilor inaltime- greutate din fisier
while (! in.eof() )
{
getline (in, line);
for (i=0; i<=line.size(); i++)
{
if (line[i] != ' ' ) numar.push_back( line[i] );
else
{
istringstream r( numar );
r>>y;
numar.clear();
}
}
istringstream r( numar );
r>>x;
gutui.insert ( Int_Pair ( y, x ) );
numar.clear();
k++;
}
//se parcurge multimap-ul cu key-le sortate (inaltimile in cazul nostru)
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 (H >= it->first )
{
//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;
}
out<<max;
in.close();
out.close();
return 0;
}