De ce contează?
La o competiție, organizatorul vrea să dea premiile rapid: locul 1, locul 2, locul 3. Dacă lasă concurenții amestecați, trebuie să caute de fiecare dată cel mai bun rămas — greoi. Dar dacă îi așază mai întâi în ordinea potrivită, premierea devine o simplă plimbare de la stânga la dreapta. Sortarea inteligentă nu rezolvă ea problema; ea aranjează datele așa încât fiecare pas următor să fie evident. Toată arta e să alegi DUPĂ CE anume îi așezi.
Ideea-cheie
Știi deja să sortezi (sort din STL) și să scrii un comparator. Întrebarea pe care
o consolidează această punte nu e cum sortezi, ci după ce sortezi. Foarte multe
probleme se rezolvă brusc ușor „dacă sortezi după lucrul potrivit" — și exact
opusul: după criteriul greșit, aceeași problemă rămâne grea.
Reflexul de antrenat: nu te întreba „cum aranjez datele", ci „ce ordine face DECIZIA URMĂTOARE ușoară și locală?". Adică: după ce le-am așezat, vreau să pot merge o singură dată de la stânga la dreapta și să decid corect la fiecare element, uitându-mă doar la el și la ce am strâns până acum — fără să mă mai întorc.
Alege ordinea care transformă o alegere globală („care e cel mai bun din toți cei rămași?") într-o decizie locală evidentă („îl iau sau nu pe ăsta de aici?"). Un criteriu bun preschimbă o problemă grea într-o singură parcurgere simplă. Dacă după sortare tot trebuie să cauți înainte și înapoi, probabil ai sortat după cheia greșită.