Η Μεγαλύτερη Χωρητικότητα - capacity [25 Μονάδες]
Οι πολιτικοί μηχανικοί του ΕΜΠ χρειάζονται τη βοήθειά μας! Θέλουν να κατασκευάσουν μια σειρά από φράγματα και, προτού ξεκινήσουν τις εργασίες, πρέπει να υπολογίσουν την μέγιστη δυνατή ποσότητα νερού που μπορεί να αποθηκευτεί ανάμεσα στις διάφορες βουνοκορφές. Για λόγους απλοποίησης, θεωρούμε ότι έχουμε \(N\) κορυφές τοποθετημένες σε ίσες αποστάσεις μεταξύ τους. Η κάθε κορυφή \(i\) βρίσκεται στη θέση \(i\) και έχει ύψος \(h_i\). Επιλέγοντας δύο κορυφές \(i\) και \(j\), με \(i < j\), σχηματίζεται μαζί με το έδαφος μια ορθογώνια δεξαμενή, όπως φαίνεται στο Σχήμα 1 (δεν μας πειράζει αν παρεμβάλλονται άλλες βουνοκορφές ενδιάμεσα).
Η στάθμη του νερού δεν μπορεί φυσικά να ξεπεράσει την χαμηλότερη από τις κορυφές που σχηματίζουν την ορθογώνια δεξαμενή. Για τις ανάγκες του προβλήματος θεωρούμε τη χωρητικότητα ως το εμβαδόν του ορθογωνίου που σχηματίζεται από την δεξαμενή.
ύψος
8 | # #
7 | #~~~~~~~~~~~~~~~~~~~#~~~~~~~# ύψος νερού = 7
6 | #~~~#~~~~~~~~~~~~~~~#~~~~~~~#
5 | #~~~#~~~~~~~#~~~~~~~#~~~~~~~#
4 | #~~~#~~~~~~~#~~~#~~~#~~~~~~~#
3 | #~~~#~~~~~~~#~~~#~~~#~~~#~~~#
2 | #~~~#~~~#~~~#~~~#~~~#~~~#~~~#
1 |# #~~~#~~~#~~~#~~~#~~~#~~~#~~~#
+--------------------------------- θέση
0 1 2 3 4 5 6 7 8
Σχήμα 1: Παράδειγμα για μια σειρά από κορυφές: \(h = [1, 8, 6, 2, 5, 4, 8, 3, 7]\). Οι κορυφές στις θέσεις 1 και 8 σχηματίζουν τη δεξαμενή μέγιστης χωρητικότητας. Η απόστασή τους είναι \(8 - 1 = 7\) και το ύψος του νερού είναι 7, επομένως η χωρητικότητα είναι \(7 \cdot 7 = 49\).
Σημείωση: στο πρωτότυπο το Σχήμα 1 είναι γράφημα με ράβδους και γραμμοσκιασμένη δεξαμενή· εδώ οι κορυφές σημειώνονται με
#και το νερό με~.
Γράψτε ένα πρόγραμμα το οποίο παίρνει από την πρότυπη είσοδο στην πρώτη γραμμή το πλήθος \(N\) των κορυφών και στην δεύτερη γραμμή τα \(N\) ακέραια ύψη των κορυφών \(h_0, h_1, \ldots, h_{N-1}\) και υπολογίζει τη μέγιστη δυνατή χωρητικότητα που μπορεί να σχηματιστεί από μία δεξαμενή καθώς και τις κορυφές ανάμεσα στις οποίες θα εμφανιστεί αυτή η χωρητικότητα. Ο αλγόριθμός σας θέλουμε να είναι σωστός αλλά και αποδοτικός.
Ποια είναι η χρονική και η χωρική πολυπλοκότητα της λύσης σας; Αιτιολογήστε σύντομα την απάντησή σας (8/25 της βαθμολογίας).
Παράδειγμα εκτέλεσης ακολουθεί:
$ cat mountains.txt
9
1 8 6 2 5 4 8 3 7
$ ./capacity < mountains.txt
Maximum Capacity between mountains at positions 1 and 8: (8-1) * 7 = 49
Η χωρητικότητα του ζεύγους \((i, j)\) είναι \((j - i) \cdot \min(h_i, h_j)\)· ο έλεγχος
όλων των ζευγών είναι σωστός αλλά \(O(N^2)\), οπότε ξεκινήστε από αυτόν και μετά
ψάξτε κάτι γρηγορότερο. Σκεφτείτε δύο δείκτες θέσης, έναν σε κάθε άκρο, που κινούνται
ο ένας προς τον άλλον: ποιον από τους δύο δεν έχει νόημα να κρατήσετε, αφού κάθε
μετακίνηση μικραίνει το πλάτος; Θυμηθείτε να κρατάτε και τις θέσεις του καλύτερου
ζεύγους, να ελέγχετε την τιμή επιστροφής της scanf και να δεσμεύσετε τον πίνακα
ανάλογα με το \(N\).
Αριθμός στον οδηγό: Α25.17
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2026-sep-q5 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2026-sep-q5.html ·
Markdown (GitHub)