34ος ΠΔΠ Α' Φάση: Οι εκλογές (voting) - Λύση

Επεξήγηση εκφώνησης

Μας δίνονται \(K\) ψήφοι για τους \(M\) υποψήφιους και πρέπει να βρούμε ποιοι από τους υποψηφίους μπορούν να κερδίσουν τις εκλογές, δεδομένου ότι μένουν ακόμα \(N - K\) ψήφοι να καταμετρηθούν.

Λύση

Χωρίζουμε το πρόβλημα σε δύο βήματα:

1. Βρίσκουμε τον αριθμό ψήφων που έχει πάρει ο κάθε υποψήφιος.
2. Ελέγχουμε για κάθε υποψήφιο αν μπορεί να κερδίσει τις εκλογές με τις ψήφους που έχει συγκεντρώσει.

Βήμα 1: Για να μετρήσουμε τις ψήφους του κάθε υποψηφίου κρατάμε έναν πίνακα \(cnt[1..M]\) και κάθε φορά που βλέουμε ότι ο \(i\)-οστός υποψήφιος πήρε ψήφο, κάνουμε \(\texttt{++}cnt[i]\).

   // Μετράμε τις ψήφους για κάθε υποψήφιο.
   for (long i = 0; i < K; ++i) {
      long cur;
      fscanf(fi, "%ld", &cur);
      ++cnt[cur];
   }

Βήμα 2: Έστω ότι ο μέγιστος αριθμός ψήφων που έχει λάβει κάποιος υποψήφιος είναι \(max\_val\). Η πιο ευνοϊκή εξέλιξη της ψηφοφορίας για τον \(i\)-οστό υποψήφιο είναι να κερδίσει όλες τις υπόλοιπες \(N - K\) ψήφους.

Υπο αυτές τις συνθήκες οποιοσδήποτε ψηφοφόρος μπορεί να κερδίσει αν παίρνοντας όλες τις υπόλοιπες \(N - K\) ψήφους, ξεπερνάει το \(max\_val\), δηλαδή ο \(i\)-οστός υποψήφιος μπορεί να κερδίσει αν \(cnt[i] + N - K > max\_val\).

Επιπλέον αν υπάρχει μόνο ένας που προηγείται, δηλαδή μόνο ένας υποψήφιος έχει \(max\_val\) ψήφους, τότε προφανώς μπορεί να κερδίσει πχ παίρνοντας όλες τις υπόλοιπες \(N - K\) ψήφους (δηλαδή κερδίζει και όταν \(N = K\)).

Στην υλοποίησή μας ξεκινάμε βρίσκοντας τον μέγιστο αριθμό ψήφων \(max\_val\) και το πλήθος \(max\_cnt\) των υποψηφίων που τον έχουν.

   long max_val = -1, max_cnt = 0;
   for (long i = 1; i <= M; ++i) {
      if (cnt[i] == max_val) ++max_cnt;
      else if (cnt[i] > max_val) {
         max_val = cnt[i];
         // Βρήκαμε καινούργια μέγιστη τιμή, άρα
         // πρέπει να ξαναρχίσουμε τον μετρητή.
         max_cnt = 1;
      }
   }

Έπειτα με βάση αυτό αποφασίζουμε αν μπορεί ένας υποψήφιος να κερδίσει τις εκλογές.

   // Μετράμε τους υποψήφιους που μπορούν να κερδίσουν.
   long possible_winners = 0;
   for (long i = 1; i <= M; ++i) {
      if (max_val == cnt[i] && max_cnt == 1) ++possible_winners;
      else if (cnt[i] + N - K > max_val) ++possible_winners;
   }

Ο αλγόριθμος μας χρειάζεται \(\mathcal{O}(K + M)\) χρόνο και \(\mathcal{O}(Μ)\) μνήμη.

Σημείωση 1: Μπορούμε να συμπτύξουμε τις πρώτες δύο επαναλήψεις σε μία (δείτε τον κώδικα εδώ).

Σημείωση 2: Μπορούμε να καταμετρήσουμε τις ψήφους χρησιμοποιώντας map ή unordered map, αλλά επειδή το \(M\) είναι σχετικά μικρό, η χρήση πίνακα είναι αρκετά αποδοτική.