Î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

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 t₁, t₂, …, t_n, 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

Explicație

Se vor repara masinile 2, 3 şi 5, cu timpii de reparaţie 2, 4 şi 2.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Masini:

#include <fstream>
using namespace std;

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

int n, T;
int t[1000];

void Citeste();
int NrMasini();  // Greedy
void Sort();

int main()
{
    Citeste();
    Sort();
    fout << NrMasini();
    return 0;
}

void Citeste()
{
    fin >> n >> T;
    for ( int i = 0; i < n; ++i )
        fin >> t[i];
}

int NrMasini()
{
    int k = 0; // nr de masini care vor fi reparate
    int timp = 0;

    for ( int i = 0; i < n && timp + t[i] <= T; ++i )
        if ( timp + t[i] <= T )
        {
            timp += t[i];
            k++;
        }
    return k;
}

void Sort()
{
    int aux;
    for ( int i = 0; i < n - 1; ++i )
        for ( int j = i + 1; j < n; ++j )
            if ( t[i] > t[j] )
            {
                aux = t[i];
                t[i] = t[j];
                t[j] = aux;
            }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #91 Masini

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #91 Masini de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #91 Masini