Màxim en Finestra

Donada una seqüència de N enters i una mida de finestra W, per a cada
posició i de la seqüència cal trobar el màxim de la finestra que acaba a
i. La finestra conté els elements des de la posició max (0, i − W + 1)
fins a i (ambdós inclosos).

Per resoldre aquest problema de manera eficient, farem servir una cua de
prioritat (en el nostre cas, un max-heap) que emmagatzema parelles
(valor, índex). Definim l’struct:

    struct Elem {
        int valor;
        int index;
    };

amb la comparació:

    bool operator>(const Elem& a, const Elem& b) {
        return a.valor > b.valor;
    }

La tècnica per poder fer això de forma eficient és la següent. Per a
cada nou element de la seqüència, el fiquem a la cua de prioritat.
Després, mentre l’element del cim tingui un índex fora de la finestra
(és a dir, index <= i - W), el traiem. El màxim actual de la finestra
serà, doncs, el valor del cim de la cua de prioritat.

Aquesta tècnica s’anomena “esborrat mandrós” (lazy deletion): els
elements que ja no pertanyen a la finestra no s’eliminen immediatament,
sinó que es treuen només quan arriben al cim del heap. Això fa que
l’algorisme sigui molt eficient en la pràctica.

Entrada

La primera línia conté un enter W (W ≥ 1), la mida de la finestra. A
continuació, una seqüència d’enters separats per espais fins al final de
l’entrada.

Sortida

Per a cada posició de la seqüència (començant per la primera), el màxim
de la finestra corresponent, un per línia.

Observació

Aquest és un problema d’eficiència. Una solució ingènua que recorri tota
la finestra per a cada posició no passarà els casos de prova grans, però
la solució amb una cua de prioritat sí.

Has d’enviar un fitxer program.cc que inclogui "heap.hh". Als fitxers
públics trobaràs heap.hh i assert.hh.

Informació del problema

Autoria: Pau Fernández

Generació: 2026-03-05T11:27:37.502Z

© Jutge.org, 2006–2026.
https://jutge.org
