Sto cercando di risolvere Ordine Online delle OII 2020. Sto avendo problemi nel capire da che “menù” incominciare. Dato che non mi è venuto nulla in mente, ho messo un while loop che crea tutte le combinazioni possibili tra i menù (ad esempio la prima combinazione sarà antipasti, pizze, dessert la seconda sarà antipasti, dessert, pizze e così via) con la funzione next_permutation . La funzione solve ha due cicli: uno sul vettore di vettori (vettore di menù) e l’altro su i prezzi dei piatti del menù stesso. Se un piatto dello stesso prezzo non è già stato scelto (cioè non è contenuto nel set) allora aggiungo il prezzo al set, altrimenti passa al menù dopo.
Non è sicuramente una soluzione “elegante” ma non capisco perché non dovrebbe funzionare.
Il correttore non mi dà nessun TLE ma solo WA. Il codice è il seguente:
#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> vs)
{
set<int> s; // uso un set per capire se il piatto dal prezzo vs[i][j] sia già stato preso o meno
for(int i = 0; i < (int)vs.size(); ++i)
{
for(int j = 0 ; j < (int)vs[0].size(); ++j)
{
if(s.find(vs[i][j]) == s.end()) s.insert(vs[i][j]); // se non è già stato preso allora aggiungi il vassoio al set
else break; // altrimenti passa al prossimo vettore
}
}
return s.size(); // il risultato è il numero totale di vassoi presi, cioè la lunghezza del set
}
int conta(int N, vector<int> &A, vector<int> &P, vector<int> &D)
{
int res = 0;
vector<vector<int>> vs = { A, P, D }; // ho messo i vecttori dati in un vettore per poter generare tutte le permutazioni
sort(vs.begin(), vs.end()); // sort necessario per next_permutations()
do {
res = max(res, solve(vs)); // il risultato è il massimo tra il risultato precedente e il risultato calcolato con solve()
}while(next_permutation(vs.begin(), vs.end())); // genera tutte le permutazioni del vettore di vettori
return res;
}