Cerința

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[i], înălțimile persoanelor în ordinea inițială, să se afișeze numărul minim de case pe care managerul trebuie să le deschidă.

Date de intrare

În fișierul gogosi.in se află pe prima linie numărul N iar pe a doua line N numere naturale, A[i] reprezentând înălțimea persoanei i din coadă inițială.

Date de ieșire

Afișați pe prima linie din fișierul gogosi.out numarul minim de case care trebuie deschise.

Restricții și precizări

1 ≤ N ≤ 10⁶
1 ≤ A[i] ≤ 10⁵
1 ≤ A[i] ≤ 2 pentru teste în valoare de 20 puncte.
1 ≤ N ≤ 10³ pentru teste în valoare de alte 30 puncte.

Exemplu

gogosi.in

7
1 4 2 3 9 7 6

gogosi.out

Explicație

Numărul minim de case care trebuie deschise este 3. Există mai multe variante de a împărți persoanele, una dintre acestea este:
Coada 1: i 1 2 5 (persoanele din sirul initial) A[i]: 1 4 9 (inaltimile lor)
Coada 2: i 3 6 (persoanele din sirul initial) A[i]: 2 7 (inaltimile lor)
Coada 3: i 4 7 (persoanele din sirul initial) A[i]: 3 6 (inaltimile lor)

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema gogosi:

#include <fstream>
#include <vector>

using namespace std;

ifstream cin("gogosi.in");
ofstream cout("gogosi.out");

vector<int> v;

int main(){
    
    int n; cin >> n;
    for(int i = 0; i < n; i ++){
        
        int a; cin >> a;
        
        int l = 0, r = v.size() - 1;
        while(l <= r){
            
            int mid = (l + r) / 2;
            if(v[mid] <= a)  r = mid - 1;
            else            l = mid + 1;
        }
        
        if(l == v.size())   v.push_back(a);
        else                v[l] = a;
    }
    
    cout << v.size();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2297 gogosi

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2297 gogosi de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2297 gogosi