# DreamTeam Selection 15/100

**URL:** <https://forum.olinfo.it/t/dreamteam-selection-15-100/7133>\
**Category:** Aiuto\
**Created:** [24 Marzo 2022, 7:04pm UTC](https://forum.olinfo.it/t/dreamteam-selection-15-100/7133 "2022-03-24T19:04:42Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![FrancescoFam](https://forum.olinfo.it/user_avatar/forum.olinfo.it/francescofam/32/1455_2.png) [@FrancescoFam](https://forum.olinfo.it/u/FrancescoFam)\
**Post date:** [24 Marzo 2022, 7:04pm UTC](https://forum.olinfo.it/t/dreamteam-selection-15-100/7133/1 "2022-03-24T19:04:43Z")

</div>

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

```auto
#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.

---

<div class="post-metadata">

**Author:** ![iRom](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/i/9fc29f/32.png) [@iRom](https://forum.olinfo.it/u/iRom)\
**Post date:** [24 Marzo 2022, 9:13pm UTC](https://forum.olinfo.it/t/dreamteam-selection-15-100/7133/2 "2022-03-24T21:13:41Z")

</div>

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()`](http://cplusplus.com/reference/algorithm/sort/) che ha complessita’ `O(n log(n))` e togliere i primi `giocatori - giocatori_da_scegliere` della lista