Vereinheitlichen der Gebäudehöhen
Um die Kosten zu senken, hat sich die städtische Planungsabteilung an Sie gewandt, damit alle Gebäude auf eine einheitliche Höhe gebracht werden. Wenn sämtliche Gebäude die gleiche Höhe haben, sinken die Baukosten erheblich.
In der Stadt stehen
n Gebäude mit unterschiedlichen Höhen zur Verfügung. Wenn Sie die Höhe eines Gebäudes um x verändern, wird dafür ein Meeting nötig, das x Minuten dauert. Da Sie wenig Zeit haben, möchten Sie die dafür aufgewendete Meeting-Zeit so gering wie möglich halten. Wie viel Zeit werden Sie dabei mindestens investieren müssen?Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).In der nächsten Zeile stehen
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ), die die Anfangshöhen der Gebäude darstellen.Ausgabe
Das Programm soll eine einzelne ganze Zahl ausgeben – die minimale Zeit, die für die Meetings erforderlich ist.
Beispiele
Eingabe | Ausgabe |
5
1 4 8 2 9 | 14 |
Erklärung
Die optimale Höhe ist 4 ⇒ Wir müssen 1 → 4 (3-Minuten-Meeting), 2 → 4 (2-Minuten-Meeting), 8 → 4 (4-Minuten-Meeting) und 9 → 4 (5-Minuten-Meeting) ändern ⇒ insgesamt 14 Minuten.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB