Buogiorno, ho provato a completare il problema delle nazionali coda per il buffet, riuscendo ha stampare sempre l’output corretto ma mi va in TLE. La mia idea e’ di memorizzare il numero di partecipanti che arriva al buffet per ogni secondo e poi tramite delle condizioni decidere se prenderle tutte o se alcune mandarle dal paninaro. Creedo di aver capito che il problema e’ che ci mette O(n^2) ma non riesco a capire come fare con un solo ciclo. Riuscireste a spiegarmi il ragionamento dietro?
#include <vector>
#include <algorithm>
using namespace std;
vector <int> cucina (int N, int K, int X, vector<int> H){
vector <int> prefix(X);
vector <int> kitchen(X);
sort(H.begin(), H.end());
int pos = 0, counter;
for (int i = 0; i < X; i++){
int inCoda = 0;
for (int j = i; j < X; j++){
if (i == 0){
counter = 0;
while (H[pos] == j){
counter++;
pos++;
}
prefix[j] = counter;
}
if (inCoda + prefix[j] > K)
inCoda = K;
else
inCoda += prefix[j];
if (inCoda > 0){
inCoda--;
kitchen[i]++;
}
}
}
return kitchen;
}