Rezolvare completă PbInfo #1057 MaxP

Considerăm un şir de numere a1, a2, …, aN. O secvenţă nevidă în acest şir este de forma ai, ai+1, …, aj, unde i ≤ j. De exemplu, pentru N=4 şi şirul 2 3 4 3, secvenţele nevide sunt: 2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3, 3. Definim puterea unui element ai ca fiind numărul de secvenţe care-l conţin pe ai şi în care ai este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul 2 3 4 3 puterea elementului a1 este 1 (fiind maxim doar în secvenţa formată din el însuşi), a elementului a2 este 2 (a2 fiind maxim în secvenţele 2 3 şi 3), a elementului a3 este 6 (fiind maxim în secvenţele 2 3 4, 2 3 4 3, 3 4, 3 4 3, 4 şi 4 3), iar a elementului a este 1.

Cerinţe

Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.

Date de intrare

Fișierul de intrare maxp.in conține pe prima linie numărul natural N, iar pe a doua linie, în ordine, numerele naturale a1, a2, …, aN separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire maxp.out va conține pe prima linie un număr natural ce reprezintă puterea cea mai mare a unui element din şirul dat şi pe a doua linie va conţine un număr natural ce reprezintă numărul de elemente din şir care au cea mai mare putere.

Restricții și precizări

  • 2 <= N <= 200.000
  • Elementele şirului sunt numere naturale şi au cel mult 6 cifre

Exemplul 1

maxp.in

7
9 3 4 5 1 2 2

maxp.out

12 
1

Explicație

Elementul 5 de pe poziţia 4 este maxim în 12 secvenţe:
3 4 5, 3 4 5 1, 3 4 5 1 2, 3 4 5 1 2 2, 4 5,
4 5 1, 4 5 1 2, 4 5 1 2 2, 5, 5 1, 5 1 2,
5 1 2 2, deci puterea lui este 12. Este singurul element care are această putere, celelalte elemente având puteri mai mici.

Exemplul 2

maxp.in

6
1 0 7 7 2 6

maxp.out

3 
2

Explicație

Elementele din poziţiile 3 şi 4 sunt maxime în 3 secvenţe, deci puterea lor este 3. Celelalte elemente au puteri mai mici.

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 MaxP:

// O(n) - 100 puncte - prof.Dan Pracsiu
#include<fstream>
#include<iostream>
#define inFile  "maxp.in"
#define outFile "maxp.out"
#define dim 200001

using namespace std;

int a[dim], st[dim], dr[dim], q[dim], poz[dim], n;

int main()
{
    int i, k, x, nrsol;
    long long p, pmax;
    //citire
    ifstream fin(inFile);
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
    
    // constructie st
    k = 0;
    q[k] = dim + 2;
    poz[k] = 0;
    st[k] = 0;
    for (i = 1; i <= n; i++)
    {
        x = a[i];
        while (q[k] < x) k--;
        st[i] = i - poz[k] - 1;
        k++;
        q[k] = x;
        poz[k] = i;
    }
    
    // constructie dr
    k = 0;
    q[k] = dim + 2;
    poz[k] = n + 1;
    dr[k] = 0;
    for (i = n; i >= 1; i--)
    {
        x = a[i];
        while (q[k] < x) k--;
        dr[i] = poz[k] - i - 1;
        k++;
        q[k] = x;
        poz[k] = i;
    }

    // calcul
    nrsol = 1;
    pmax = (st[1] + 1);
    pmax *= (dr[1] + 1);
    for (i = 2; i <= n; i++)
    {
        p = (st[i] + 1);
        p = (p * (dr[i] + 1));
        if (p > pmax)
        {
            pmax = p;
            nrsol = 1;
        }
        else if (p == pmax) nrsol++;
    }
    
    ofstream fout(outFile);
    fout << pmax << "
" << nrsol << "
";
    fout.close();
    
    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 #1057 MaxP

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1057 MaxP 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!