Pe o scândură se găsesc înfipte și aliniate N cuie de diverse înălțimi, măsurate în centimetri.

La fiecare “bătaie” de ciocan într-un cui, acesta pătrunde în scândură cu 1 cm. Tâmplarul dorește să obțină cea mai lungă secvență de cuie de aceeași înălțime, după aplicarea a cel mult M “bătăi” de ciocan.

Cerința

Să se determine lungimea maximă – L a unei secvențe de cuie de aceeași înălțime în condițiile date și numărul minim de “bătăi” – K necesare obținerii acesteia.

Date de intrare

Fișierul de intrare cuie.in conține pe prima linie două numere naturale nenule N și M și pe următoarea linie N valori naturale nenule ce reprezintă înălțimile celor N cuie măsurate în cm.

Date de ieșire

Fișierul de ieșire cuie.out va conține pe prima linie două numere naturale nenule L și K, separate printr-un spațiu, ce reprezintă: L – lungimea maximă a unei secvențe de cuie cu aceeași înălțime, respectiv K – numărul minim de ”bătăi” de ciocan necesare pentru obținerea secvenței maxime.

Restricții și precizări

1 ≤ N ≤ 500.000
1 ≤ M ≤ 500.000
1 ≤ K ≤ M
1 ≤ înălțime cui ≤ 100.000 cm
înălțimea unui cui reprezintă lungimea părții aflate în afara scândurii.

Exemplu

cuie.in

8 5
3 2 4 3 3 5 3 1

cuie.out

5 3

Explicație

Secvența de lungime maximă se obține după 3 “bătăi”, efectuate asupra cuielor 3 și 6: 3 2 3 3 3 3 3 1.

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

/*
    prof. Eugen Nodea
    Complexitate : O(n) / deque / parsare
*/
# include <cstdio>
# include <cstdlib>
# include <deque>
# define NMax 500005
using namespace std;

const int Lim = 1 << 16;
deque <int> d;
int i, j, n, m, st, dr, Lmax;
long long costAct, costMinn;
int H[NMax], costMaxim;
int pos =  Lim - 1;
char s[Lim];

void Next()
{
    if (++pos == Lim)
        fread(s, 1, Lim, stdin), pos = 0;
}
void Get(int &x)
{
    for (; s[pos] < '0' || s[pos] > '9'; Next());
    for (x = 0; s[pos] >= '0' && s[pos] <= '9'; Next())
        x = x * 10 + s[pos] - '0';
}
void bagaDeque(int poz)
{
    while (d.size() && H[poz] <= H[d.back()])
        d.pop_back();

    d.push_back(poz); ++dr;
}

bool avanseaza(int poz)
{
    int minn;
    if (d.size()) minn=H[d.front()];
             else minn=H[poz];

    if (H[poz] >= minn) { /// aduc H[poz] la inaltimea minimului
        long long costNou = costAct + (H[poz] - minn);
        if (costNou <= costMaxim) {
            bagaDeque (poz);
            costAct = costNou;
            return 1;
        } else return 0;
    } else { /// in acest caz trebuie sa le aduc pe toate celelate la inaltimea H[poz]
             /// - toate anterioarele sunt la inaltimea minn
             /// --> desi imi trebuie (minn - H[poz]) * NMax scanduri batai
         long long costNou = costAct + 1LL * (minn - H[poz]) * (dr - st + 1);
         if (costNou <= costMaxim) {
            bagaDeque (poz);
            costAct = costNou;
            return 1;
        } else return 0;
    }
}

void scoate(int poz)
{
    int minn;
    if (d.front() == poz) d.pop_front();

    if (d.size()) minn=H[d.front()];
             else minn=H[poz];
    int Hact = H[poz]; /// cel pe care il scot

    if (Hact >= minn) { /// Hact era adus la inaltimea minn prin (Hact - minn) stocniri
        costAct -= (Hact - minn);
        ++st;
    } else { /// Hact era minimul pe acea secventa
             /// --> asta inseamna ca toate celelate elemente erau aduse la inaltimea Hact
             /// --> desi le urcam pe toate la inaltimea minn
        costAct -= 1LL * (dr - st) * (minn - Hact);
        ++st;
    }
}

int main ()
{
    int x;

    freopen("cuie.in",  "r", stdin);
    freopen("cuie.out", "w", stdout);

    Get(n);  Get(costMaxim);

    for (int i=1; i<=n; ++i){
        Get(x);
        H[i] = x;
    }

    st = 1; costAct = 0;
    /// mereu stiu lungimea si costul ca sa fac o subseventa maximala
    /// care se termina pe pozitia i
    for (int i=1; i<=n; ++i) {
        while (! avanseaza (i)) {
            scoate(st);
        }
        if (dr - st + 1 > Lmax) Lmax = dr - st + 1, costMinn = costAct;
        else if (dr - st + 1 == Lmax && costAct < costMinn) costMinn = costAct;
    }

    printf("%d %lld\n", Lmax, costMinn);

    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 #1736 Cuie

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