Ecluza este o construcție hidrotehnică amenajată pe traseul unei căi navigabile, care asigură trecerea navelor între două suprafețe de apă cu niveluri diferite. O ecluză se compune dintr-un bazin numit “sas” sau “camera ecluzei”, prevăzut la ambele capete cu porţi etanşe şi dintr-o instalaţie puternică de pompare pentru umplerea sau golirea sasului până la nivelul dorit.

Specialiștii români au construit pe cursul navigabil al Dunării o succesiune de N ecluze numerotate de la 1 la N, care asigură condiții optime de navigare în sezoanele secetoase. Astfel, dacă o navă se află la un moment dat în ecluza i și nivelul apei din ecluză diferă de nivelul apei din ecluza i+1, pentru a-și continua navigarea în condiții optime se face modificarea nivelului apei fie din ecluza i la nivelul ecluzei i+1, fie se face modificarea nivelului apei din ecluza i+1 la nivelul ecluzei i.

De exemplu, dacă pentru un sector navigabil există 9 ecluze pentru care nivelul apei este următorul:

ecluză:	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`
nivel apă:	`2`	`2`	`4`	`1`	`2`	`2`	`1`	`2`	`2`

numărul minim de ecluze la care se impun modificări ale nivelului apei este 3, după cum urmează:

nivelul din ecluza 3 este coborât până la nivelul 2
ecluza 4 este umplută până la nivelul 2
ecluza 7 este umplută până la nivelul 2

Cerinţă

Cunoscând nivelul apei din cele N ecluze, să se determine numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Date de intrare

Fişierul de intrare ecluze.in conține pe prima linie numărul natural N ce reprezintă numărul de ecluze. Pe următoarea linie se află h[1], h[2],…, h[N] valori naturale separate prin câte un spațiu ce reprezintă nivelul apei corespunzător fiecărei ecluze.

Date de ieșire

Fişierul de ieșire ecluze.out va conţine pe o singură linie un număr natural M ce reprezintă numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Restricții și precizări

2 ≤ N ≤ 100.000
1 ≤ h[i] ≤ 1.000 (h[i] – nivelul apei ecluzei i)
pentru 20% din teste N ≤ 30

Exemplu

ecluze.in

9
1 2 3 3 2 1 1 2 3

ecluze.out

Explicație

ecluza 1 este umplută până la nivelul 2
ecluza 2 este umplută până la nivelul 3
nivelul din ecluza 4 este coborât până la nivelul 2
nivelul din ecluza 5 este coborât până la nivelul 1
ecluza 7 este umplută până la nivelul 2
ecluza 8 este umplută până la nivelul 3

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

/*
    ecluze - O(n) 100 p
    prof. Eugen Nodea
*/
# include <fstream>
# include <algorithm>
# define NM 100005
# define inf 999999999
using namespace std;

ifstream f("ecluze.in");
ofstream g("ecluze.out");

int i, j, n, m;
int Min[NM], last[NM], urm[NM], a[NM];

int main ()
{
    f >> n;
    for (i=1; i<=n; ++i)
    {
        f >> a[i];
        Min[i] = inf;
    }

    for (i=n; i>=1; --i)
        if (last[a[i]] == 0) last[a[i]] = i;
                        else urm[i] = last[a[i]], last[a[i]] = i;

    Min[1] = 0;
    for (i=1; i<=n; ++i)
    {
        if (i>1)    Min[i] = min(Min[i], Min[i-1] + 1);
        if (urm[i]) Min[urm[i]] = min(Min[urm[i]], Min[i] + (urm[i] - i - 1));
    }

    g << Min[n] << "
";

    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 #1242 Ecluze

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