Se dă un șir a[1], a[2], …, a[n] de numere naturale și un număr natural k.

Cerința

Să se determine cele mai mari k numere din șir.

Date de intrare

Programul citește de la tastatură numerele n, k, A, B, C, D. Șirul de numere se va genera după formulele:

a[1] = A
a[i] = (B * a[i-1] + C) % D, pentru i=2..n

Date de ieșire

Programul va afișa pe ecran, ordonate crescător, cele mai mari k numere din șir.

Restricții și precizări

1 ≤ n ≤ 5.000.000
1 ≤ k ≤ min(100.000, n)
1 ≤ A, B, C, D ≤ 1.000.000.000

Exemplu

Intrare

10 4 13 23 47 97

Ieșire

55 56 74 96

Explicație

Se obține șirul de numere a = (13, 55, 51, 56, 74, 3, 19, 96, 24, 17). Cele mai mari patru numere sunt 55, 56, 74, 96.

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

#include <iostream>
using namespace std;

int h[100003], k;

void Coboara(int p) /// O(log n)
{
    int fiu;
    while (p <= k / 2)
    {
        fiu = 2 * p;
        if (fiu + 1 <= k && h[fiu + 1] < h[fiu])
            fiu++;
        if (h[p] <= h[fiu]) return;
        swap(h[p], h[fiu]);
        p = fiu;
    }
}

/// Functie care organizeaza vectorul h[]
/// ca un min-heap
void MakeHeap()
{
    for (int i = k / 2; i >= 1; i--)
        Coboara(i);
}

void Citire()
{
    int i, n, A, B, C, D;
    cin >> n >> k >> A >> B >> C >> D;
    h[1] = A;
    for (i = 2; i <= k; i++)
    {
        A = (1LL * B * A + C) % D;
        h[i] = A;
    }
    MakeHeap();

    for (i = k + 1; i <= n; i++)
    {
        A = (1LL * B * A + C) % D;
        if (A > h[1])
        {
            h[1] = A;
            Coboara(1);
        }
    }
}

void Afisare()
{
    while (k > 1)
    {
        cout << h[1] << " ";
        h[1] = h[k];
        k--;
        Coboara(1);
    }
    cout << h[1] << "\n";
}

int main()
{
    Citire();
    Afisare();
    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 #3011 lastk

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