26ος ΠΔΠ B' Φάση: Ρυθμική γυμναστική (ensemble) - Λύση

Λύση

Ο μέσος όρος των στοιχείων \(A[0], .. ., A[N-1]\) είναι \(\frac{A[0]+ ... + A[N-1]}{N}\).

Για τον A) τύπου μέσο όρο, πρέπει να αφαιρέσουμε τις \(K\) μικρότερες και τις \(K\) μεγαλύτερες τιμές και να πάρουμε τον μέσο όρο των υπόλοιπων στοιχείων. Ο βέλτιστος τρόπος για να το κάνουμε αυτό είναι ταξινομώντας τον πίνακα και υπολογίζοντας τον μέσο όρο των \(A[K], ..., A[N-K-1]\).

Για το πρώτο παράδειγμα, ο ταξινομημένος πίνακας είναι:

και θέλουμε τον μέσο όρο των \(N-2\cdot K\) bold στοιχείων (που είναι \(8.07\)).

Για τον Β) τύπου μέσο όρο, πρέπει να αντικαταστήσουμε τις \(K\) μικρότερες και τις \(K\) μεγαλύτερες τιμές με τις κοντινότερές τους τιμές. Για τις μικρότερες τιμές αυτή είναι η \(A[K]\) (\(=6.4\) στο παράδειγμα) και η \(A[N-K-2]\) (\(= 9.1\) στο παράδειγμα).

Ο αλγόριθμος έχει πολυπλοκότητα \(\mathcal{O}(N \log N)\) (λόγω της ταξινόμησης) και μνήμη \(\mathcal{O}(N)\).

Σημείωση: Η συνθήκη \(K \leq \frac{N-1}{2}\) εγγυάται ότι αφού αφαιρέσουμε \(2K\) στοιχεία, ο πίνακας δεν θα είναι άδειος.

#include <algorithm>
#include <cstdio>

const long MAXN = 100'000;

double A[MAXN];

int main() {
   FILE *fi = fopen("ensemble.in", "r");
   long N, K;
   fscanf(fi, "%ld %ld", &N, &K);
  
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%lf", &A[i]);
   }
  
   std::sort(A, A+N);
  
   double sum1 = 0.0;
   double sum2 = 0.0;
  
   for (long i = 0; i < N; ++i) {
      if (i < K) {
         sum2 += A[K];
      } else if (i > N - K -1) {
         sum2 += A[N-K-1];
      } else {
         sum1 += A[i];
         sum2 += A[i];
      }
   }
   fclose(fi);
  
   FILE *fo = fopen("ensemble.out", "w");
   double av1 = sum1 / double(N - 2 * K);
   double av2 = sum2 / double(N);
   fprintf(fo, "%.2lf %.2lf\n", av1, av2);
   fclose(fo);
   return 0;
}

Τέλεια ακρίβεια (προαιρετικό)

Αν χρησιμοποιήσουμε floats αντί για doubles, τότε λόγω περιορισμένης ακρίβειας θα χάσουμε ένα testcase. Αν και στο συγκεκριμένο πρόβλημα είναι αρκετό να χρησιμοποιήσουμε doubles, μπορούμε να αποφύγουμε τελείως την ανακριβή αναπαράσταση.

Αφού κάθε στοιχείο έχει ακρίβεια ενός δεκαδικού ψηφίου, το άθροισμα θα έχει πάντοτε ακρίβεια ενός δεκαδικού ψηφίου. Για την διαίρεση μας ενδιαφέρουν δύο δεκαδικά στοιχεία στο αποτέλεσμα, άρα πρέπει να υπολογίσουμε με ακρίβεια τριών και να στρογγυλοποιήσουμε αναλόγως. Συνεπώς, χρειαζόμαστε τρία δεκαδικά ψηφία.

Το τρικ είναι να πολλαπλασιάσουμε επί \(1000\), ώστε τα στοιχεία να είναι ακέραιοι με την ελάχιστη ακρίβεια που χρειαζόμαστε. Αθροίζουμε κανονικά και έπειτα διαιρούμε με το πλήθος των στοιχείων. Στο παράδειγμα θα πάρουμε άθροισμα \(48400\) και μέσο όρο \(8066\). Αποκωδικοποιώντας την απάντηση, παίρνουμε \(8.066\). Βλέπουμε ότι το τελευταίο ψηφίο είναι μεγαλύτερο ή ίσο από \(5\) και προσθέτουμε \(0.01\) στο υπόλοιπο, λαμβάνοντας \(8.07\). Δείτε τον παρακάτω κώδικα για λεπτομέρειες.

#include <algorithm>
#include <cstdio>

const long MAXN = 100'000;

long A[MAXN];

void print_value(FILE *fo, long val) {
   long decimal = val / 10;
   if (val % 10 >= 5) {
      decimal++;
   }
   long first_two = decimal / 100;
   long last_two = decimal % 100;
   fprintf(fo, "%ld.%02ld", first_two, last_two);
}

int main() {
   FILE *fi = fopen("ensemble.in", "r");
   long N, K;
   fscanf(fi, "%ld %ld", &N, &K);
  
   for (long i = 0; i < N; ++i) {
      double temp;
      fscanf(fi, "%lf", &temp);
      A[i] = temp * 1000;
   }
  
   std::sort(A, A+N);
  
   long sum1 = 0;
   long sum2 = 0;
  
   for (long i = 0; i < N; ++i) {
      if (i < K) {
         sum2 += A[K];
      } else if (i > N - K -1) {
         sum2 += A[N-K-1];
      } else {
         sum1 += A[i];
         sum2 += A[i];
      }
   }
   fclose(fi);
  
   FILE *fo = fopen("ensemble.out", "w");
   long av1 = sum1 / (N - 2 * K);
   long av2 = sum2 / N;
   print_value(fo, av1);
   fprintf(fo, " ");
   print_value(fo, av2);
   fprintf(fo, "\n");
   fclose(fo);
   return 0;
}