Ho risolto Gambling Assistant, con l’utlizzo di priority queue, lascio qua il codice.
#include <iostream>
#include <queue>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
long long min = -1;
long long considering = 0;
long long total = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < N; i++) {
long long tmp;
cin >> tmp;
if (considering < K) {
considering++;
total += tmp;
pq.push(tmp);
if (min > tmp || min == -1) {
min = tmp;
}
} else {
if (min < tmp) {
total -= min;
pq.pop();
total += tmp;
pq.push(tmp);
min = pq.top();
}
}
cout << total << " ";
}
}
Ma va comunque in TLE, nell’ultimo case del subtask 2,3 e negli ultimi dell’ultimo.
Non so come potrei ancora ottimizzarlo, qualcuno mi da una manina?
Grazie :D
(so che in realtà quei long long non sono necessari ma in un momento di disperazione li ho messi)
In che modo posso sfruttare i constraints?
N <= 100.000.000
K <= N
Ci <= 13
Non mi dicono nulla
L’unica cosa che riesco a pensare è, nel caso in cui min = 13 allora non potrà avere una mano migliore di quella, ma basta solo quello?
Un insieme di 13 contatori per avere la distribuzione delle carte in mano ed il totale pesato di tali distribuzioni potrebbero servire. All’arrivo di ogni carta non dovrebbe essere lungo aggiornare contatori e totale. Come tecnica direi una variante dello “sliding windows”.
Perdona l’ignoranza, ma non ho capito di cosa tu stia parlando.
Ho capito che cos’è la sliding window, e anche l’implementazione, l’ho già usata prima, ma non capisco il nesso tra quella e il problema.
Qua si tratta di sostituire la carta peggiore che hai in mano con quella che peschi, a meno che quella che peschi non sia peggiore di tutte quelle che hai.
Potresti spiegarti meglio?
Supponi che il numero di carte in mano sia 6 e che tu abbia due 4, un 7 e tre 10, totale 3x10+7+2x4 peschi dal mazzo un 7 a questo punto scarti un 4 la nuova situazione dei contatori sarà … ed il totale sarà variato di …
Lascia pure la priority-queue per altri problemi qui bastano i 13 contatori delle carte che ha in mano il giocatore e aggiornamento della singola situazione in O(1) contro O(log(k)).
Ciao, so che è passato parecchio tempo ma oggi ho provato comunque a rifarlo e faccio sempre 60/100
Questo è il codice che ho scritto:
// #include <fstream>
#include <iostream>
#include <vector>
using namespace std;
int get_min(vector<int> a) {
for (int i = 0; i < a.size(); i++) {
if (a[i] != 0) return i;
}
return -1;
}
int main() {
// ifstream cin("input.txt");
int N, K;
cin >> N >> K;
vector<int> counter(13 + 1, 0);
int found = 0;
int total = 0;
for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
if (found != K) {
counter[tmp]++;
total += tmp;
found++;
} else {
int min_found = get_min(counter);
if (tmp > min_found) {
counter[min_found]--;
total -= min_found;
counter[tmp]++;
total += tmp;
}
}
cout << total << " ";
}
}
gli output sono giusti, è sempre il TLE il problema.
Grazie mille, purtroppo non avevo idea di cosa facessero queste cose e anche dopo aver letto la documentazione non ne sono molto sicuro, potresti spiegarmi nel dettaglio cosa fanno?
Grazie ancora.