Două maxime distincte din fișier la BAC: C++

Cele mai mari două valori distincte dintr-un fișier pot fi găsite fără sortare și fără memorarea tuturor numerelor. Păstrezi cel mai mare candidat și cel mai mare candidat strict mai mic decât el. La fiecare citire actualizezi aceste două locuri, ignorând repetările care nu aduc o valoare distinctă nouă.

La BAC, diferența dintre „cele mai mari două elemente” și „cele mai mari două valori distincte” este esențială. În secvența nouă, nouă, șapte, două elemente maxime pot avea ambele valoarea nouă. Cele două valori distincte cerute aici sunt însă nouă și șapte. Citește această precizare și în subiectele de examen.

Formatul fișierului din această lecție

Fișierul bac.in conține numere întregi, de cel mult un miliard în valoare absolută, separate prin spații sau linii noi. Nu există un număr de elemente scris înaintea datelor. Citim până când nu mai poate fi extras un număr.

Fișierul poate fi gol sau poate conține o singură valoare distinctă. În aceste cazuri, programul va afișa mesajul „nu exista”. Alegem explicit acest comportament pentru exemplul nostru; într-o problemă de BAC trebuie respectat mesajul sau convenția cerută acolo.

Nu interpreta primul număr drept lungime dacă enunțul nu spune asta. Pentru un fișier care începe cu șapte, doi, nouă, valoarea șapte este un element al șirului. Alegerea greșită a formatului afectează toate prelucrările următoare.

De ce două inițializări cu zero nu sunt suficiente

Dacă toate numerele sunt negative, zero nu este un candidat valid. Pentru minus opt, minus trei și minus cinci, cele mai mari două valori distincte sunt minus trei și minus cinci. Un program care pornește cu două maxime zero poate păstra valori care nici nu apar în date.

Vom folosi doi indicatori logici care spun dacă fiecare loc a fost ocupat. Valorile numerice inițiale ale variabilelor nu reprezintă candidați până când indicatorul corespunzător devine adevărat.

Această abordare separă existența unui rezultat de valoarea lui. Zero, minus unu sau orice alt număr din domeniu pot fi date legitime, deci nu trebuie folosite fără justificare ca semnale de absență.

Cele trei situații de actualizare

Dacă nu avem încă un maxim, prima valoare citită ocupă acel loc. Dacă valoarea nouă este mai mare decât maximul, vechiul maxim devine al doilea candidat, iar valoarea nouă devine maxim.

Dacă valoarea nouă este strict mai mică decât maximul, ea poate îmbunătăți al doilea loc. O acceptăm dacă nu există încă un al doilea candidat sau dacă este mai mare decât candidatul de acolo.

Dacă valoarea nouă este egală cu maximul, o ignorăm pentru scopul acestei probleme. Nu trebuie să punem aceeași valoare și pe al doilea loc, deoarece cele două rezultate trebuie să fie distincte.

Exemplu urmărit pe tabel

Secvența este patru, nouă, nouă, șase, doisprezece, opt. Simbolul „absent” arată că nu avem încă două valori distincte.

Valoare citită	Maxim	Al doilea maxim distinct
4	4	absent
9	9	4
9	9	4
6	9	6
12	12	9
8	12	9

Când apare doisprezece, vechiul maxim nouă este mai bun decât orice candidat anterior pentru locul al doilea. De aceea, îl mutăm direct acolo. Valoarea opt de la final nu schimbă nimic, fiind mai mică decât al doilea maxim deja cunoscut.

Program C++ complet

Presupunem că fișierul există și conține numai numere în domeniul declarat și separatori albi. Programul afișează rezultatele în ordine descrescătoare dacă există două valori distincte.

#include <fstream>
#include <iostream>
using namespace std;

int main() {
    ifstream fin("bac.in");
    long long x, maxim = 0, alDoilea = 0;
    bool existaMaxim = false, existaAlDoilea = false;
    while (fin >> x) {
        if (!existaMaxim || x > maxim) {
            if (existaMaxim) {
                alDoilea = maxim;
                existaAlDoilea = true;
            }
            maxim = x;
            existaMaxim = true;
        } else if (x < maxim &&
                   (!existaAlDoilea || x > alDoilea)) {
            alDoilea = x;
            existaAlDoilea = true;
        }
    }
    if (existaAlDoilea) cout << maxim << ' ' << alDoilea;
    else cout << "nu exista";
    return 0;
}

Condiția buclei verifică succesul citirii. Astfel, corpul se execută numai pentru o valoare extrasă efectiv. Spațiile și liniile noi de la final nu determină prelucrarea încă o dată a ultimei valori.

O variantă care testează doar faptul că nu s-a ajuns încă la sfârșit, apoi încearcă citirea în corp, poate procesa o valoare veche după o citire eșuată. Leagă prelucrarea direct de succesul extragerii, ca în program.

De ce vechiul maxim coboară pe locul al doilea

Presupunem că noua valoare este strict mai mare decât toate cele citite anterior. Vechiul maxim este cel mai mare dintre valorile vechi. Prin urmare, după introducerea noului maxim, el devine automat cea mai mare valoare distinctă rămasă.

Nu trebuie comparat din nou cu vechiul al doilea candidat, deoarece era deja mai mare decât el. Ordinea dintre cele două locuri era o proprietate menținută de algoritm.

Dacă noua valoare este sub maxim, primul loc rămâne corect. Trebuie verificat doar dacă ea este un candidat mai bun pentru al doilea loc. Cele două ramuri acoperă toate valorile distincte noi, iar egalitatea cu maximul nu adaugă informație utilă.

Verificarea existenței rezultatului

După prima valoare citită, avem un maxim, dar nu avem încă un al doilea maxim distinct. După o repetare a aceleiași valori, situația rămâne neschimbată. Numărul elementelor citite nu este suficient pentru a garanta două valori distincte.

De exemplu, un fișier cu o mie de apariții ale lui cinci nu are un al doilea maxim distinct. În schimb, un fișier cu numai două valori diferite are deja ambele rezultate. Indicatorul pentru al doilea candidat exprimă exact condiția necesară.

Această separare este utilă și în alte probleme de selecție: minimul numerelor pozitive, prima valoare care respectă o proprietate sau cel mai bun candidat dintr-o categorie posibil goală. Ea înlocuiește o presupunere fragilă cu o explicație clară a stării.

Complexitate și alegerea metodei

Fiecare valoare este citită o singură dată și produce un număr constant de comparații. Timpul este liniar în numărul elementelor din fișier. Memoria suplimentară este constantă, indiferent cât de lung este fișierul.

Sortarea ar necesita păstrarea datelor și o muncă suplimentară care nu este necesară pentru numai două extreme. Un vector de frecvență ar fi nepotrivit pentru domeniul foarte mare de valori întregi declarat aici.

Dacă cerința ar solicita toate valorile în ordine sau multe ranguri diferite, alegerea metodei s-ar putea schimba. Eficiența trebuie raportată la rezultatul cerut, nu la o preferință generală pentru o anumită tehnică.

Exerciții cu răspunsuri

Pentru zece, zece, șapte, nouă, rezultatul este zece și nouă. Repetarea lui zece nu ocupă locul al doilea, iar nouă înlocuiește candidatul șapte.

Pentru minus nouă, minus doi, minus cinci, rezultatul este minus doi și minus cinci. Testul verifică faptul că zero nu rămâne candidat artificial.

Pentru trei, trei, trei, nu există două valori distincte. Programul afișează mesajul de absență, chiar dacă au fost citite trei elemente.

Pentru zero, minus unu, rezultatul este zero și minus unu. Ambele sunt date valide și nu trebuie confundate cu semnale de absență.

Pentru unu, doi, trei, patru, la fiecare maxim nou, vechiul maxim coboară pe locul al doilea. Rezultatul final este patru și trei.

Întrebări frecvente

Pot folosi aceeași metodă pentru cele mai mici două valori?

Da, adaptând sensul comparațiilor și păstrând aceeași distincție între existența candidatului și valoarea lui. Verifică separat egalitățile și ordinea celor două locuri.

Contează câte numere sunt pe o linie?

Pentru citirea numerică folosită aici, spațiile și liniile noi sunt separatori. Programul prelucrează aceeași secvență de valori indiferent de împărțirea lor pe linii, în formatul declarat.

Cum verific o soluție înainte de examen?

Testează duplicate ale maximului, numai valori negative, o singură valoare distinctă și un fișier gol. Pentru feedback pe ramurile de actualizare, poți discuta programul la meditații de informatică.