Problema bufale

Aiuto
1

Buonasera, è da qualche giorno che cerco di risolvere questo problema. Per risolverlo ho pensato di dare a Paola il voto in cui la differenza tra il voto di Monica e Paola è minimo, facendo ciò riesco a risolvere l’input di esempio ma sottoponendo il codice solo appunto l’esempio e il primo case della subtask 4 danno esito positivo, quindi mi chiedevo se l’approccio con cui ho affrontato il problema è sbagliato.

long long solve(int N, int* Ma, int* Pa) {

  int contM = 0;
    int contP = 0;
    vector<int> M(N), P(N), differenze(N);

    for (size_t i = 0; i < N; i++)
    {
        if (Ma[i] > Pa[i])
        {
            contM++;
        }
        else
        {
            contP++;
        }
    }

    long long int risultato = 0;
    long long int Monica = 0;
    long long int Paola = 0;
    if (contM == contP)
    {
        for (size_t i = 0; i < N; i++)
        {
            risultato += Ma[i] + Pa[i];
        }
    }
    else
    {
        if (contM > contP)
        {
            for (int i = 0; i < N; i++)
            {
                M[i] = Ma[i];
                P[i] = Pa[i];
                differenze[i] = M[i] - P[i];
            }

            while (contM != contP)
            {
                vector<int>::iterator minIt = min_element(differenze.begin(), differenze.end());
                int min = *minIt;

                if (min < 0)
                {

                    Paola += P[distance(differenze.begin(), minIt)];
                    differenze.erase(differenze.begin() + distance(differenze.begin(), minIt));
                    M.erase(M.begin() + distance(differenze.begin(), minIt));
                    P.erase(P.begin() + distance(differenze.begin(), minIt));
                }
                else
                {

                    contP++;
                    contM--;
                    Paola += P[distance(differenze.begin(), minIt)];
                    M.erase(M.begin() + distance(differenze.begin(), minIt));
                    P.erase(P.begin() + distance(differenze.begin(), minIt));
                }
            }
            for (int i = 0; i < M.size(); i++)
            {
                Monica += M[i];
            }
        }
        else
        {
            for (int i = 0; i < N; i++)
            {
                M[i] = Ma[i];
                P[i] = Pa[i];
                differenze[i] = P[i] - M[i];
            }

            while (contM != contP)
            {
                vector<int>::iterator minIt = min_element(differenze.begin(), differenze.end());
                int min = *minIt;

                if (min < 0)
                {
                    Monica += M[distance(differenze.begin(), minIt)];
                    differenze.erase(differenze.begin() + distance(differenze.begin(), minIt));
                    M.erase(M.begin() + distance(differenze.begin(), minIt));
                    P.erase(P.begin() + distance(differenze.begin(), minIt));
                }
                else
                {
                    risultato--;
                    contP--;
                    contM++;
                    Monica += P[distance(differenze.begin(), minIt)];
                    M.erase(M.begin() + distance(differenze.begin(), minIt));
                    P.erase(P.begin() + distance(differenze.begin(), minIt));
                }
            }
            for (int i = 0; i < P.size(); i++)
            {
                Paola += P[i];
            }
        }
    }

    risultato += Monica + Paola;

    return risultato;
}
2

Ho cambiato il codice,utilizzando sempre la stessa logica ma ottimizzandolo ed ora faccio 93 punti su 100, un solo case non dà esito positivo: il secondo della subtask 2. Il codice usato è il seguente:

long long solve(int N, int* Ma, int* Pa)
{
    struct Mozzarelle
    {
        int Persona;
        int differenza;

        bool operator<(const Mozzarelle &b) const
        {
            return differenza < b.differenza;
        }
    };

    

    int contP = 0;
    int contM = 0;
    int uguali = 0;
    for (int i = 0; i < N; i++)
    {
        if (Ma[i] == Pa[i])
        {
            uguali++;
        }
        else if (Ma[i] > Pa[i])
        {
            contM++;
        }
        else
        {
            contP++;
        }
    }

    long long int risultato = 0;
    if (contM == contP)
    {
        for (int i = 0; i < N; i++)
        {
            if (Ma[i] > Pa[i])
            {
                risultato += Ma[i];
            }
            else if (Pa[i] > Ma[i])
            {
                risultato += Pa[i];
            }
        }

        int t = 2;
        int j = 0;
        while (uguali > 0)
        {
            if (t % 2 == 0)
            {
                risultato += Ma[j];
            }
            else
            {
                risultato += Pa[j];
            }

            t++;
            j++;
            uguali--;
        }
    }
    else
    {
        vector<Mozzarelle> a;
        if (contM > contP)
        {
            for (int i = 0; i < N; i++)
            {
                a.push_back({Pa[i], Ma[i] - Pa[i]});
            }

            sort(a.begin(), a.end());

            int i = 0;
            while (contM != contP)
            {
                int min = a[i].differenza;

                if (min < 0)
                {
                    risultato += a[i].Persona;
                }
                else if (min > 0)
                {
                    risultato += a[i].Persona;
                    contP++;
                    contM--;
                }
                else
                {
                    risultato += a[i].Persona;
                    contP++;
                }

                i++;
            }

            for (i; i < N; i++)
            {
                risultato += a[i].differenza + a[i].Persona;
            }
        }
        else
        {
            for (int i = 0; i < N; i++)
            {
                a.push_back({Ma[i], Pa[i] - Ma[i]});
            }

            sort(a.begin(), a.end());

            int i = 0;
            while (contM != contP)
            {
                int min = a[i].differenza;

                if (min < 0)
                {
                    risultato += a[i].Persona;
                }
                else if (min > 0)
                {
                    risultato += a[i].Persona;
                    contP--;
                    contM++;
                }
                else
                {
                    risultato += a[i].Persona;
                    contM++;
                }

                i++;
            }

            for (i; i < N; i++)
            {
                risultato += a[i].differenza + a[i].Persona;
            }
        }
    }

    return risultato;
}
3

Ciao, potresti essere interessato a questa ottimizzazione.

4

Ho risolto in questo modo:

long long solve(int N, int *Ma, int *Pa)
{
    struct Mozzarelle
    {
        int Monica;
        int differenza;

        bool operator<(const Mozzarelle &b) const
        {
            return differenza < b.differenza;
        }
    };

    vector<Mozzarelle> a;

    for(int i = 0;i<N;i++)
    {
        a.push_back({Ma[i],Ma[i]-Pa[i]});
    }

    sort(a.rbegin(),a.rend());

    long long int risultato = 0;

    for(int i = 0;i<N/2;i++)
    {
        risultato += a[i].Monica;
    }

    for(int i = N/2;i<N;i++)
    {
        risultato += a[i].Monica - a[i].differenza;
    }

    return risultato;

}
5

gg, puoi abbassare ulteriormente la complessità da \mathcal{O}(n \log n) a \mathcal{O}(n) sostituendo std::nth_element a std::sort, ma con il server più veloce a quanto pare non è più necessario.