Î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.

Î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.

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ă.

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ă.

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).

#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;
}