I pochi risultati che non vanno fuori tempo risultano corretti, se qualcuno potrebbe aiutarmi ad ottimizzare il codice sottostante ne sarei grato.
#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>
#define MAXN 100000
using namespace std;
struct offer
{
int grade;
long long ants;
int price;
float ppa;
};
long long antnum(int n)
{
if((n==0)||(n==1))
return 1;
else{
return antnum(n-1)+antnum(n-2);
}
}
bool comp(offer a, offer b)
{
return a.ppa>=b.ppa;
}
int T, N, K, i, j;
int A[MAXN], B[MAXN];
long long ris=0;
vector<offer> vett;
int main() {
//freopen("input0.txt", "r", stdin);
//freopen("output0.txt", "w", stdout);
assert(1 == scanf("%d", &T));
for(i=0; i<T; i++) {
assert(2 == scanf("%d %d", &N, &K));
vett.resize(N);
for (j=0; j<N; j++)
{
assert(2 == scanf("%d %d", &A[j], &B[j]));
vett[j].grade=A[j];
vett[j].price=B[j];
vett[j].ants=antnum(A[j]);
vett[j].ppa=vett[j].price/vett[j].ants;
}
j=0;
sort(vett.begin(), vett.end(), comp);
while(j<vett.size())
{
if(K-vett[j].ants>=0)
{
ris=ris+vett[j].price;
K=K-vett[j].ants;
}
else j++;
}
printf("%lld\n", ris);
ris=0;
vett.clear();
}
return 0;
}
Ho creato un vettore dinamico di strutture “offer” contenenti ognuna grado della colonia, valore, numero di formiche e valore per formica. Lo ordino poi in base al valore per formica e controllo dalla prima offerta (migliore) se può essere comprata: in tal caso aggiorno il risultato, se no vado alla prossima offerta.
Grazie in anticipo.