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 } }