32ος ΠΔΠ Α' Φάση: Πρόγραμμα ανταλλαγής φοιτητών Erasmus+ (erasmus) - Λύση

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

Μας δίνονται \(N\) πανεπιστήμια και \(M\) φοιτητές. Κάθε πανεπιστήμιο \(i\) δηλώνει πόσους φοιτητές \(X_i\) μπορεί να δεχτεί. Κάθε φοιτητής \(j\) έχει πετύχει κάποια μόρια \(B_j\), και έχει δηλώσει το πολύ \(10\) πανεπιστήμια στα οποία θέλει να περάσει, με τη σειρά προτίμησής του.

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

Λύση

Παρατηρούμε ότι σύμφωνα με τις προδιαγραφές του προβλήματος, η θέση όπου θα καταλήξει ένας φοιτητής εξαρτάται μόνο από τα Πανεπιστήμια κι από τους φοιτητές που πέτυχαν περισσότερα μόρια από αυτόν. Για παράδειγμα το πανεπιστήμιο όπου θα καταλήξει ένας φοιτητής που πέτυχε 18.000 μόρια δεν εξαρτάται καθόλου από τους φοιτητές που πέτυχαν 17.000 μόρια.

Έτσι, προκύπτει φυσικά η ανάγκη να ταξινομήσουμε τους φοιτητές σε φθίνουσα σειρά, έτσι ώστε πρώτος να βρίσκεται αυτός με τα περισσότερα μόρια και τελευταίος αυτός με τα λιγότερα. Κατόπιν, επεξεργαζόμαστε τους φοιτητές με αυτή τη σειρά. Κάθε φορά που επεξεργαζόμαστε έναν φοιτητή \(i\), ελέγχουμε μία-μία τις επιλογές του, από την προτιμότερη προς την πιο ανεπιθύμητη. Όταν βρούμε ένα Πανεπιστήμιο το οποίο έχει ανοιχτή θέση για τον φοιτητή, τον στέλνουμε εκεί, και ενημερώνουμε το Πανεπιστήμιο να μειώσει κατά μία τις ανοιχτές του θέσεις.

Παρακάτω δίνεται μία ενδεικτική υλοποίηση των όσων περιγράφηκαν.

#include <bits/stdc++.h>
using namespace std;

int N, M;
int A[1010];
int ans[10010];
pair<int,int> B[10010];
vector <int> P[10010];

int main() {
  #ifdef CONTEST
    freopen("erasmus.in", "r", stdin);
    freopen("erasmus.out", "w", stdout);
  #endif
    scanf("%d %d", &N, &M);

    int i, j, pan, S, K, in;
    for(i=0;i<N;i++) scanf("%d", &A[i]);
    for(i=0;i<M;i++) {
        scanf("%d %d", &S, &K);
        for(j=0;j<K;j++) {
            scanf("%d", &pan);
            P[i].push_back(pan-1);
        }
        B[i] = make_pair(S, i);
    }
    sort(B, B+M, greater< pair<int,int> >());
    
    bool gotin = false;
    for(i=0; i<M; i++) {
      in = B[i].second;      
      gotin = false;
      for(j=0;j<P[in].size();j++) {
	if( A[ P[in][j] ]>0){
	  A[ P[in][j] ]--;
	  ans[in] = P[in][j];
	  gotin = true;
	  break;
	}
      }
      if(!gotin) ans[in] = -1;
    }

    for(i=0;i<M;i++) {
        if(ans[i]!=-1)
            printf("%d\n", ans[i]+1);
        else
            printf("NONE\n");
    }
}