gogosi (Pbinfo #2297)

Link către problemă: #gogosi.

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.

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

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?

Algoritmul

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Acest site folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.

septembrie 2019
L Ma Mi J V S D
 1
2345678
9101112131415
16171819202122
23242526272829
30