ZADATAK MAJSTORI — REŠENJE

Opis rešenja

Rešenje koristi vektor za čuvanje broja eksera u svakoj kutiji. Nakon učitavanja svih vrednosti, vektor se sortira u rastućem redosledu pomoću funkcije sort() iz zaglavlja <algorithm>.

Pošto je potrebno pronaći dve kutije sa najmanjim brojem eksera, dovoljno je sabrati prva dva elementa sortiranog vektora. Nakon sortiranja, upravo se na pozicijama 0 i 1 nalaze dve najmanje vrednosti.

U programu se koristi vector<int>, jer broj kutija nije unapred poznat. Elementi se dodaju u vektor funkcijom push_back(), a zatim se vektor sortira pozivom sort(kv.begin(), kv.end()).

Ideja algoritma

1. Učitati broj kutija n.
2. Učitati broj eksera iz svake kutije i smestiti ga u vektor.
3. Sortirati vektor od najmanjeg ka najvećem elementu.
4. Uzeti prva dva elementa sortiranog vektora.
5. Sabrati ih i ispisati rezultat.

Ključna ideja je da posle sortiranja ne moramo posebno da tražimo najmanje dve vrednosti. One se već nalaze na početku vektora.

Kompletno C++ rešenje

// ZADATAK MAJSTORI - REŠENJE
// Rešenje pomoću vektora i sortiranja

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, in;
    int z = 0;

    // Vektor u koji ćemo smestiti broj eksera
    // koji se nalazi u svakoj kutiji.
    vector<int> kv;

    // Učitavamo broj kutija.
    cin >> n;

    // Učitavamo broj eksera iz svake kutije.
    for (int i = 0; i < n; i++)
    {
        cin >> in;

        // Dodajemo učitanu vrednost na kraj vektora.
        kv.push_back(in);
    }

    // Sortiramo vektor u rastućem redosledu.
    // Posle sortiranja najmanje vrednosti
    // nalaze se na početku vektora.
    sort(kv.begin(), kv.end());

    // Sabiramo prva dva, odnosno dva najmanja elementa.
    for (int i = 0; i < 2; i++)
    {
        z += kv[i];
    }

    // Ispis rezultata.
    cout << z << endl;

    return 0;
}
    

Objašnjenje koda

1. Zaglavlja programa
<iostream> omogućava rad sa standardnim ulazom i izlazom, <vector> omogućava korišćenje vektora, a <algorithm> sadrži funkciju sort().

2. Čuvanje podataka
Promenljiva kv je vektor celih brojeva. Svaki njegov element predstavlja broj eksera u jednoj kutiji. Funkcija push_back() dodaje novu vrednost na kraj vektora.

3. Sortiranje
Naredba sort(kv.begin(), kv.end()) sortira sve elemente vektora od najmanjeg ka najvećem.

4. Izbor dve najmanje vrednosti
Posle sortiranja, kv[0] je najmanja vrednost, a kv[1] je druga najmanja vrednost. Zato se mogu direktno sabrati.

5. Složenost
Učitavanje podataka zahteva O(n) operacija, dok sortiranje pomoću std::sort zahteva O(n log n) poređenja. Ukupna vremenska složenost je zato O(n log n).

Važna napomena

Ovo rešenje je jednostavno i pregledno, ali za nalaženje samo dve najmanje vrednosti nije neophodno sortirati ceo vektor. Moglo bi se napraviti i rešenje koje jednim prolaskom kroz podatke pronalazi dve najmanje vrednosti, čime bi vremenska složenost bila O(n).

Ipak, primena sort() je veoma korisna za učenje jer pokazuje kako se standardni C++ algoritmi mogu kombinovati sa kontejnerom vector.

Korisni resursi

• std::vector — cppreference — dokumentacija za C++ vektor.
• std::sort — cppreference — dokumentacija i primeri za sortiranje elemenata.
• C++ Algorithms — cppreference — pregled standardne biblioteke algoritama.

Posebno je korisno proučiti vector, push_back(), begin(), end() i sort(), jer se ove funkcije i konstrukcije veoma često koriste u takmičarskom C++ kodu.

---

Povratak
|< Kvalifikacije za okružna takmičenja

---