# PBinfo #2150 – credite – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Maria este studentă în anul I la facultatea de informatică și a primit o listă de N probleme, numerotate de la 1 la N, pe care trebuie să le rezolve la cursul de algoritmică, rezolvarea unei probleme durând exact o unitate de timp. Pentru că profesorul vrea să testeze capacitatea elevilor de a a face cele mai bune alegeri, pentru fiecare problemă acesta a stabilit numărul de credite (Ci) pe care studentul le va primi dacă rezolvă problema i, dar și un număr limită de unități de timp (Ti) până la care problema poate fi rezolvată.

Cerința
Cunoscând numărul de probleme, numărul de credite al fiecărei probleme precum și timpul limită de rezolvare al fiecărei probleme, scrieți un algoritm care determină numărul maxim de credite pe care le poate obține Maria.

Date de intrare
Pe prima linie a fișierului de intrare credite.in se găsește un număr natural N, reprezentând numărul de probleme de pe listă.
Pe următoarele N linii din fișierul de intrare vor fi datele despre fiecare problemă, pe linia i+1 găsindu-se 2 numere naturale Ci și Ti care reprezintă numărul de credite, respectiv timpul limită pentru problema i.

Date de ieșire
În fișierul credite.out se va afișa un singur număr natural, reprezentând numărul maxim de credite pe care Maria le poate obține.

Restricții și precizări

2 ≤ n ≤ 10000
2 ≤ Ci ≤ 1000
1 ≤ Ti ≤ 10000

Exemplu:
credite.in

4
10 3
7 5
8 1
2 1
credite.out

25
Explicație
Maria alege să rezolve problema 3, renunțând la problema 4 pentru ca are mai puține credite și același timp limită ca problema 3. După aceea va rezolva problemele 1 și 2, adunând în total 25 de credite.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
#define N_MAX 10005
ifstream f("credite.in");
ofstream g("credite.out");
struct problema {
	int c, t;
	/// suprascriem operatorul < pentru compararea dupa nr de credite a elementelor din coada de prioritati
	/*bool operator<(problema const& p) const
	{
		return c < p.c;
	}*/
};
bool Compare(problema a, problema b) /// functie pentru compararea dupa nr de credite a elementelor din coada de prioritati
{
    return a.c < b.c;
}
bool sort_by_t(problema const& a, problema const& b) /// functie care sorteaza descrescator dupa deadline
{
	return a.t > b.t;
}
problema v[N_MAX];
int main() {
	int n;
	f>>n;
	for (int i = 0; i < n; i++)
		f>>v[i].c>>v[i].t;
	sort(v, v + n, sort_by_t); /// sortam descrescator dupa deadline
	/// Indexul problemei care a devenit disponibila (cand time scade
	/// sub timpul limita t al unei probleme, spunem ca problema a devenit disponibila)
	int curpb = 0;
	/// Totalul de credite obtinute
	int total = 0;
	/// Retine problemele disponibile care n-au fost inca programate
	priority_queue<problema, vector<problema>,bool (*)(problema,problema)> q(Compare);
	for (int time = 10000; time >= 1; time--)
    {
		/// Gasim toate problemele care devin disponibile la timpul time si le punem intr-o coada
		while (curpb < n && time <= v[curpb].t)
        {
			q.push(v[curpb]);
			curpb++;
		}
		/// Daca o problema e disponibila o luam pe cea mai buna si o rezolvam la timpul time
		/// adaug numarul de credite la total
		if (q.size() > 0)
        {
			total += q.top().c;
			q.pop();
		}
	}
	g<<total;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2150)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2150/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2150/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)