Question

La magazinul X sunt N persoane așezate la coadă pentru gogoși. Din cauza aglomerației, managerul
vrea să împartă persoanele la mai multe case. Deoarece toată lumea trebuie să vadă gogoșile,
înălțimea fiecărei persoane trebuie să fie mai mică sau egală decât înălțimile tuturor celor de după el în
coadă lui. Mai mult, dacă persoana i în șirul inițial și persoana j în șirul inițial (i < j) ajung în aceeași
coadă, persoană i trebuie să fie înaintea persoanei j. Dându-se N, numărul de persoane și A, înălțimile
persoanelor în ordinea inițială, să se afișeze numărul minim de case pe care managerul trebuie să le
deschidă.

Answer 1

Aici poti folosi o smecherie, si anume:

1. Banuiesc ca ai un vector cu inaltimile persoanelor, daca nu ai iti faci. 

2. Presupunem ca daca se deschide o noua casa, ultimii X oameni de la coada initiala se vor duce la noua casa, iar acesti X oameni sunt in ordine crescatoare a inaltimii. Sa dau un exemplu:

Oameni: 1 2 3 4 2 3 1 2 3 4 5 2 3 4 5

Cand se deschide casa noua ar pleca de la coada initiala ultimii 4 oameni, adica 2 3 4 5, si astfel noua casa are oameni in ordine crescatoare a inaltimii, pentru ca daca ar pleca mai multi, spre exemplu 5 oameni, am lua si acel 5 din fata lui 2 si omul cu inaltime 2 nu ar mai vedea.

Deci pentru coada ce care spuneam initial: 1 2 3 4 2 3 1 2 3 4 5 2 3 4 5

Ar trebui sa se deschida case cam asa:

Casa 1: 2 3 4 5
Casa 2: 1 2 3 4 5
Casa 3: 2 3
Iar la casa initiala ar ramane doar 1 2 3 4 care sunt ok ordonati.

Deci ar trebui sa deschida 3 case. 

Acum sa observam o treaba: Daca oamenii sunt se la inceput ordonati crescator dupa inaltime atunci nu e nici o problema, problema apare cand avem un om mai inalt in fata unui om mai mic, adica un numar mai mare in fata unui numar mai mic. In cazul ala avem nevoie de o noua casa.

Asa ca tu poti pur si simplu sa parcurgi vectorul si sa verifici cate numere au un "om mai inalt"(numar mai mare) in fata lor si deci nu pot vedea. Asta o faci cu un simplu contor si cu in if in acel for. DUpa ce ai parcurs vectorul, acel contor e raspunsul tau!