Salve, sto provando a risolvere il problema “ois_lootboxes” , con il seguente codice, ma ottengo 0/100.
#include <stdio.h>
#include <assert.h>
#include <set>
// constraints
#define MAXN 5000
// input data
int N, X, i;
int P[MAXN], Q[MAXN];
int main() {
// uncomment the following lines if you want to read/write from files
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
assert(2 == scanf("%d %d", &N, &X));
for (i = 0; i < N; i++)
assert(2 == scanf("%d %d", &P[i], &Q[i]));
std::multiset<std::pair<int, int>, std::greater<std::pair<int, int>>> weighted;
for (i = 0; i < N; i++) {
weighted.insert({P[i]/Q[i], Q[i]});
}
int res = 0;
int prevRes = 0;
while (X > 0) {
for (std::multiset<std::pair<int, int>>::iterator it = weighted.begin(); it != weighted.end(); ++it) {
if ((*it).second <= X) {
X -= ((*it).second);
prevRes = res;
res += (*it).first * (*it).second;
//std::cout << (*it).first << " " << (*it).second<<std::endl;
weighted.erase(it);
break;
}
}
if (res == prevRes) {
X = 0;
}
}
printf("%d\n", res); // print the result
return 0;
}
Probabilmente è il metodo di risoluzione in sè ad essere sbagliato, qualcuno sa dirmi cosa c’è di sbagliato?
