Ho un dubbio riguardante questo problema abbastanza semplice dove ho implementato una soluzione ma volevo qualche chiarimento su quale fosse la soluzione più ottimale possibile.
Vi giro la traduzione:
Ogni dicembre, VK organizza tradizionalmente un evento per i suoi dipendenti chiamato “Secret Santa”. Ecco come accade.
All’evento partecipano i dipendenti numerati da 1 a n. Ad ogni dipendente gli viene assegnato un dipendente i diverso gli viene assegnato un dipendente j a cui deve fare un regalo di Capodanno. Ogni dipendente è assegnato esattamente a un altro dipendente e nessuno è assegnato a se stesso (ma due dipendenti possono essere assegnati tra loro).
L’assegnazione viene solitamente generata in modo casuale. Quest’anno, in via sperimentale, è stato chiesto a tutti i partecipanti all’evento chi desiderano realizzare
un regalo. Ogni dipendente ha detto di voler fare un regalo al dipendente j.
Trova un incarico valido b che massimizzi il numero di desideri soddisfatti dei dipendenti.
Ingresso
Ogni test contiene più casi di test. La prima riga contiene il numero di casi di test t (1 < t < 105). Descrizione dei casi di test
segue,
Ciascun test case è composto da due righe. La prima riga contiene un singolo intero n (2 < n < 2- 10°) — il numero di partecipanti all’evento.
La seconda riga contiene n interi ognuno dei quali equivale al desiderio dell’ennesimo elemento.
In output bisognerà mostrare il numero di dipendenti soddisfatti e la sequenza aggiornata tenendo conto che ogni dipendente ricevere massimo un regalo e non può fare un regalo a se stesso
Definisci “più ottimale”
Che dandogli grandi input ha un tempo di esecuzione il più basso possibile
Non ne sapevo l’esistenza. Grazie per il consiglio.