DreamTeam 5 / 100

Aiuto
1

il problema è la velocità, “Execution timed out” in tutte le sub task tranne i casi di esempio, qualcuno potrebbe aiutarmi a snellirlo e velocizzarlo?

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100000
#define MAXK 100000

int N, K;
vector<int>miglioriAmici(MAXN), puntiSolo(MAXN), puntiConAmico(MAXN);

int main()
{
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin >> N >> K;
    for(int i = 0; i != N; i++)
    cin >> miglioriAmici[i] >> puntiSolo[i] >> puntiConAmico[i];

    int bestP = puntiSolo[0], cnt = 0, container = 0, container2 = 0, res = 0;
    do
    {
        for(int i = 0; i < puntiSolo.size(); ++i)
        {
            if(bestP < puntiSolo[i])
            {
                bestP = puntiSolo[i]; //bestP = puntiSolo[container]
                container = i;
                container2 = miglioriAmici[i];
            }

        }

        int puntiCoppia = puntiConAmico[container] + puntiConAmico[miglioriAmici[container]]; //migliore attualmente + migliore amico del migliore attulmente considerando i punti insieme
        if(puntiCoppia >= bestP && puntiCoppia >= puntiSolo[miglioriAmici[container]]) // se la somma dei punti dei migliori amici è maggiore dei punti di ogni elemento della coppia
        {
            res += puntiCoppia;
            cnt += 2;

            puntiSolo.erase(puntiSolo.begin() + container2);
            puntiConAmico.erase(puntiConAmico.begin() + container2);
            miglioriAmici.erase(miglioriAmici.begin() + container2);

        }
        else
        {
            res += bestP;
            cnt += 1;
        }

        puntiSolo.erase(puntiSolo.begin() + container);
        puntiConAmico.erase(puntiConAmico.begin() + container);
        miglioriAmici.erase(miglioriAmici.begin() + container);
        container = container2 = bestP = 0;
    }
    while(cnt != K);

    cout << res << endl;
}
2

Ciao, a prima vista potrebbe uscire di tempo negli altri testcase perchè entra in un loop infinito nel momento in cui aggiungendo 2 a cnt, quello supera K ma il ciclo non si conclude. In secondo luogo, dovresti puntare su una soluzione greedy in cui:

  • L’amico con il punteggio migliore viene tenuto così com’è, mentre il valore dell’altro viene modificato in relazione a quanto farebbe perdere alla squadra se entrasse anche lui.

  • Punteggio dell’amico con minore valore (b) = Punteggio di b con l’amico (a) - la differenza tra il punteggio di a con e senza b

  • Scelgo greedy i primi K giocatori con punteggio più alto

Spero sia chiara la spiegazione

2 Mi Piace