Question

#91 Masini - 25 puncte, Greedy

În curtea unui atelier de reparaţii auto, sunt n maşini care trebuie sa fie reparate. Deoarece nu sunt
suficienţi mecanici, în fiecare moment de timp se poate lucra doar la o singură maşină.
Cerinţa
Cunoscând timpul necesar pentru repararea fiecărei maşini, scrieţi un program care calculează
numărul maxim de maşini care pot fi reparate într-un interval de timp T.
Date de intrare
Pagină | 7
Pe prima linie a fişierului masini.in se găsec două numere naturale n şi T separate printr-un singur
spaţiu, reprezentând numărul de maşini din curtea atelierului auto şi timpul total în care se va lucra.
Pe linia a doua, separate prin câte un spaţiu, se găsesc n numere naturale t1, t2, …, tn, reprezentând
timpii necesari pentru repararea fiecărei maşini.
Date de ieşire
Pe prima linie a fişierului masini.out se va găsi un număr natural k, reprezentând numărul maxim de
maşini care pot fi reparate.
Restricţii şi precizări
1 < n, T <= 1000
numerele de pe a doua linie a fişierului de intrare vor fi mai mici sau egale cu 100
Exemplu
masini.in
5 10
6 2 4 8 2
masini.out
3
Explicație
Se vor repara masinile 2, 3 şi 5, cu timpii de reparaţie 2, 4 şi 2

Answer 1

#include <fstream>
#include <algorithm>  //Pentru functia sort
using namespace std;

int main()
{
    ifstream fin("masini.in");
    ofstream fout("masini.out");

    int n, a[1000], s = 0, cnt = 0, T;

    fin>>n>>T;
    for(int i = 0; i < n; i++)
        fin>>a[i];

    sort(a, a + n);
    for(int i = 0; i < n; i++)
        {
            s += a[i];
            if(s <= T)
                cnt++;
            else
                break;
        }
    fout<<cnt;
    return 0;
}