Question

c++ rosnaca tablica
Limit czasu: 1,00 s Limit pamięci: 512 MB
Dostajesz tablicęnliczby całkowite. Chcesz zmodyfikować tablicę tak, aby była rosnąca, tj. każdy element był co najmniej tak duży jak element poprzedni.

W każdym ruchu możesz zwiększyć wartość dowolnego elementu o jeden. Jaka jest minimalna wymagana liczba ruchów?

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitąn: rozmiar tablicy.

Następnie druga linia zawieranliczby całkowitex1,x2, … ,xn: zawartość tablicy.

Wyjście

Wypisz minimalną liczbę ruchów.

Ograniczenia
1 ≤ n ≤ 2 ⋅105
1 ≤xja≤109
Przykład

Wejście: Wyjście:
5
3 2 5 1 7


5

Answer 1

Odpowiedź:

#include <iostream>

using namespace std;

#define ll long long

#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int n,ile_krokow = 0;

int liczby[1000001];

int main(){

   fast

   cin >> n;

   for(int i = 1;i <= n;i++){

       cin >> liczby[i];

       if(liczby[i] < liczby[i-1]){

           ile_krokow+=liczby[i-1]-liczby[i];

           liczby[i] = liczby[i-1];

       }

   }

   cout << ile_krokow;

}

Wyjaśnienie:

Jeżeli kolejny element jest mniejszy od poprzedniego, to optymalne będzie zwiększenie go do wartości tego poprzedniego elementu.