DreamTeam Selection 15/100

Aiuto
1

Tralasciando il fatto che nell’ultima subtask vado fuori tempo massimo, non riesco a capire nelle altre dove sbaglio output.

#include <iostream>
using namespace std;
int main(){
   
   unsigned long long giocatori,giocatori_da_scegliere;
   cin>>giocatori>>giocatori_da_scegliere;
   unsigned long long  amico[giocatori],punti_solo[giocatori],punti_insieme[giocatori],ok[giocatori]={0};
   for(int i=0;i<giocatori;i++)cin>>amico[i]>>punti_solo[i]>>punti_insieme[i];
   
   unsigned long long  punti_in_coppia[giocatori/2];
   unsigned long long  cnt=0;
   
   for(int i=0;i<giocatori;i++){
         if(ok[i]==0){
         punti_in_coppia[cnt]=punti_insieme[i]+punti_insieme[amico[i]];
         ok[amico[i]]=1;
         cnt++;
         }
   }
   
   unsigned long long  ok_coppia[giocatori/2]={0};
   unsigned long long  ok_singolo[giocatori]={0};
   unsigned long long  punti_parziali=0,punti_tot=0,amico1,amico2;
   
   while(giocatori_da_scegliere>0){
      punti_parziali=0;
      if(giocatori_da_scegliere>1){
         for(int i=0;i<giocatori/2;i++){
            if(punti_parziali<punti_in_coppia[i]&&ok_coppia[i]==0){
               punti_parziali=punti_in_coppia[i];
               amico1=i;
               amico2=amico[i];
            } 
         }
         ok_coppia[amico1]=1;
         ok_singolo[amico1]=1;
         ok_singolo[amico2]=1;
         punti_tot+=punti_parziali;
         giocatori_da_scegliere-=2;
      }else{
         punti_parziali=0;
         for(int i=0;i<giocatori;i++)if(punti_parziali<punti_solo[i]&&ok_singolo[i]==0)punti_parziali=punti_solo[i];
         punti_tot+=punti_parziali;
         giocatori_da_scegliere=0;
      }
   }
   
   cout<<punti_tot;
   
}

Quella che è la mia idea è di andare prima a trovare i punteggi per ogni coppia, poi di usare la coppia più prolifica e di contrassegnarla come non più utilizzabile, contrassegnando anche i due componenti della coppia. Poi, quando ne rimane solo uno vado a vedere quello non utilizzato con il punteggio più alto. Non riesco a trovare un’altro approccio al problema, anche se questo non è efficiente su tutti i testcase.

2

Credo tu abbia assunto che il numero di giocatori da scegliere sia sempre dispari, lo noto dalla riga if(giocatori_da_scegliere>1), dunque fallisce se il numero di giocatori da scegliere e’ pari

Al di la’ di questo, ti dico che il tuo codice ha complessita’ O(n^2), mentre quella richiesta e’ O(n log(n)), quindi ti propongo un altro approccio

Hint 1: Prendi il caso in cui il numero dei giocatori da prendere sia lo stesso dei giocatori totali (devi prendere tutti), come calcoli il risultato?

Hint 2: Ora puoi partire a sottrarre uno per volta tutti i giocatori di cui non hai bisogno: siccome vuoi massimizzare il punteggio totale procedi rimuovendo prima quelli con il punteggio piu’ basso / quelli che distraggono di piu’ l’amico (questa quantita’ la puoi facilmente calcolare per ogni persona)

Hint 3: Altra osservazione che ti semplifichera’ l’implementazione: Se devi scegliere uno di una coppia di amici, conviene sempre eliminare il peggiore (lo puoi dimostrare facilmente)

Hint 4: Per ogni giocatore, a seconda che sia l’amico migliore o peggiore, puoi definire un delta che ti indica come varia il punteggio se togli il membro dalla squadra

Hint 5: Ora che hai capito come calcola (se ti manca un pezzo no problem, lo scrivo nella soluzione), come scelgo i membri da eliminare guardando l’array delta? (la risposta e’ ovvia), e come lo faccio velocemente?

Soluzione:

  1. Calcolo il totale di tutti i membri
    Siccome prendendo tutti ognuno ha il proprio amico, faccio la somma punti_insieme
  2. Calcolo il delta
    Se tolgo la persona all’indice i, allora ci sono 2 casi: se e’ peggiore del suo amico (punti_solo[i] < punti_solo[amico[i]]), allora allora perdo il suo punti_insieme[i] e guadagno quello che avevo perso distraendo l’amico migliore.
    Dunque delta[i] = - punti_insieme[i] + (punti_solo[amico[i]] - punti_insieme[amico[i]])
    Al contrario se e’ l’amico migliore, vuol dire che ho gia’ necessariamente eliminato l’amico peggiore, dunque sto perdendo punti_solo[i].
    Dunque delta[i] = - punti_solo[i]
  3. Rimuovo gli elementi “piu’ svantaggiosi”:
    Per fare questo ti sara’ sufficiente ordinare la lista in modo crescente (per farlo esiste la funzione sort() che ha complessita’ O(n log(n)) e togliere i primi giocatori - giocatori_da_scegliere della lista
1 Mi Piace