CSES - Kasvava lista

Tehtäväsi on muuttaa annettu lista kasvavaksi, jolloin jokainen alkio on vähintään yhtä suuri kuin edellinen alkio. Joka siirrolla saat valita yhden alkion ja kasvattaa sitä yhdellä. Mikä on pienin mahdollinen määrä siirtoja?

Esimerkiksi kun lista on [3,2,5,1,7], optimaalinen ratkaisu on muuttaa se listaksi [3,3,5,5,7], mihin tarvitaan 5 siirtoa.

Listan jokainen alkio on kokonaisluku välillä 1 \dots 10^9 ja listassa on enintään 10^5 alkiota.

Python

Toteuta tiedostoon fixlist.py funktio changes, joka ilmoittaa pienimmän muutosten määrän.

def changes(t):
    # TODO

if __name__ == "__main__":
    print(changes([3,2,5,1,7])) # 5
    print(changes([1,2,3,4,5])) # 0
    print(changes([3,3,1,4,2])) # 4

Java

Toteuta tiedostoon FixList.java metodi changes, joka ilmoittaa pienimmän muutosten määrän.

public class FixList {
    public long changes(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        FixList f = new FixList();
        System.out.println(f.changes(new int[] {3,2,5,1,7})); // 5
        System.out.println(f.changes(new int[] {1,2,3,4,5})); // 0
        System.out.println(f.changes(new int[] {3,3,1,4,2})); // 4
    }
}