Pentru a parcuge acest articol trebuie să cunoști căutarea binară.
Rezumat enunț: Se dă un șir de numere care reprezintă înălțimile unor persoane. Aceste persoane trebuie distribuite în ordinea în care sunt citite la un număr minim de cozi astfel încăt la fiecare să fie ordonate în ordine crescătoare (nu neapărat strict).
Ce date trebuie memorate?
Faptul că descrierea problemei conține o coadă (de magazin) ne face să credem că este necesar să folosim mai multe date de tip coadă (queue). De fapt, acest lucru nu este necesar.
De ce?
În orice moment la fiecare coadă persoanele vor fi ordonate în ordine crescătoare a înălțimilor ( \(A_1\) este înălțimea persoanei cea mai scundă din față și \(A_n\), cea mai înaltă, din spate). Atunci când așezăm o persoană nouă (cu înălțimea k) la coadă trebuie să ne asigurăm că ea este mai înaltă decât toți cei care sunt deja în coadă:
\( k \geq A_n, k \geq A_{n-1}, …. k \geq A_1 \)
Coada este însă deja ordonată, deci:
\( A_n \geq A_{n-1} \geq … \geq A_1 \)
Observăm că dacă persoana nouă este mai înaltă decât ultima deja la coadă ( \( k \geq A_n \) ), ea va fi mai înaltă decât toate celelalte (prin tranzitivitate).
Prin urmare, pentru a verifica dacă putem așeza o persoană la o coadă, este suficient să știm doar înălțimea ultimei persoane deja la coadă.
În exemplul de mai sus, Gogu se poate așeza la coadă fiindcă este mai înalt decat Ioana (ultima deja la coadă) și implicit mai înalt decât toți ceilalți. Alex nu se poate așeza la coadă fiindcă este mai scunđ decât Ioana.
Crearea unei cozi noi
Este necesar să deschidem o coadă nouă dacă următoarea persoană la rând nu se poate duce la niciuna din cozile existente, ceea ce se întâmplă când aceasta este mai scundă decât ultima persoană de la fiecare coadă.
Exemplu
În exemplul de mai sus, Irina trebuie să formeze o coadă nouă, fiindcă este mai scundă decat Pavel și Ioana care sunt la cozile deja deschise.
Eficiența metodei
Să considerăm situația prezentată mai jos.
La ce coadă îl așezăm pe Alex pentru a fi eficienți?
Soluția
Să spunem că îl așezăm pe Alex la coada a doua (la care se află deja Irina).
Acum Gogu trebuie așezat la o nouă casă. Este însă posibil să îi distribuim pe cei doi la casele deja existente, astfel:
Eficiența noii distribuții constă în diferența mică de înălțime dintre Alex și Ioana (1) în comparatie cu Alex și Irina (4).
Prin urmare, pentru eficiență maximă, fiecare persoană trebuie așezată la coada la care diferența de înăltime față de ultima persoană de la acea coadă este minimă.
Algoritmul
Variabilele folosite
Datele despre ultima persoană de la fiecare coadă le vom stoca într-un vector v (inițial gol) si vom avea nevoie de o variabilă n care va ține minte câte cozi sunt deja deschise. Fiecare element din vector va reprezenta câte o casă.
Distribuția persoanelor
Pe măsură ce înălțimile sunt citite din fișier vom distribui fiecare persoană la câte o casă. Vectorul v va fi permanent sortat descrescător datorită metodei pe care o folosim. Spre exemplu:
Fiindcă vectorul este permanent sortat descrescător, vom găsi coada la care trebuie să ducem fiecare persoană folosind căutare binară:
Dacă v[mij]==x, atunci încheiem căutarea (două persoane cu aceeași înălțime pot sta la aceeași coadă care trebuie ordonată crescător, nu neapărat strict)
Dacă v[mij]>x, atunci st=mij+1
Dacă v[mij]<x, atunci dr=mij-1
Dacă dr<st, atunci cele două valori indică elementele din vector imediat mai mare, respectiv mai mică decăt valoarea pe care vrem să o inserăm, deci v[st]=x. Spre exemplu:Dacă tot nu înțelegi, simulează cu creionul pe hârtie căutarea binară!
Cazul în care trebuie făcută o coadă nouă este cel în care st==n, iar atunci trebuie să incrementăm n (numărul de cozi).
Soluția, încearcă mai întâi să rezolvi singur!
#include <fstream>
#include <vector>
using namespace std;
ifstream f("gogosi.in");
ofstream g("gogosi.out");
int v[10000],n;
void cautbin(int x)
{
int st=0,dr=n-1,mij;
while (st<=dr)
{
mij=(st+dr)/2;
if (x==v[mij])
return;
else
if (x<v[mij])
st=mij+1;
else
dr=mij-1;
}
v[st]=x;
if (st==n)
n++;
}
int main()
{
int nr,x;
f>>nr;
for (int i=0;i<nr;i++)
{
f>>x;
cautbin(x);
}
g<<n;
return 0;
}