Canottaggio - output non ottimale

Aiuto
1

Salve, ho risolto questo problema con due cicli ottenendo un 80/100 , quando ho implementato una versione col qsort ottengo solo 30.02 punti :frowning:
il codice è questo:

#include 
#include 
#include 

#define MAXN 100000

long long int F[MAXN] = {0};
long long int P[MAXN] = {0};
long long int Res[MAXN] = {0};
int N;
int K;

FILE *in,*out;



int cmp(const void *a, const void *b){
    return *(int*)b-*(int*)a;
}

int main(){
	in = fopen("input.txt","r");
	out = fopen("output.txt","w");
	
	fscanf(in,"%d %d",&N,&K);
	for( int i = 0; i < N; i++ ){
	    fscanf(in,"%lli %lli",&F[i],&P[i]);
	    Res[i] = F[i] - 3*P[i]/2;
	    Res[i] = Res[i]*(N) + i ;
	}
	
	qsort(Res,N,sizeof(long long int),cmp);
	
	for( int i = 0; i < K; i++ )
	    fprintf(out,"%d\n",Res[i]%(N)+1);
	
	
	
	fclose(in);fclose(out);
	return 0;	
}

Ho salvato l’indice dentro al numero di Res che equivale a F[i] - (3/2)P[i]. Ho utilizzato il long long per essere sicuri che Res*= N ci stasse fra i valori ma ottengo comunque un risultato basso, qualcuno mi può dare una mano ?

2

Un possibile errore potrebbe essere il fatto che utilizzi degli interi e non dei floating point. Questo potrebbe cambiare di parecchio i risultati. Poi non riesco a comprendere per quale motivo applichi la formula Res[i]*(N)+i.
Un consiglio che ti do è quello di evitare di utilizzare long long anche perchè occuperebbero memoria per niente.

3

Quello è il modo più semplice che ho trovato per ordinare gli indici insieme al valore nel qsort, mentre non capisco dovrebbe funzionare anche con gli interi, i floating point non penso mi servano, e per la memoria adesso non mi interessa :v:t3:

4

Un modo più semplice per “ricordare” gli indici secondo me sarebbe creare una
struct Cosa { long long int potere; int indice; }; e fornire una funzione tale per cui;
Cosa a < Cosa b se e solo se a.potere < b.potere;
Ovviamente fare ciò implica che
long long int Res[MAXN];
venga sostituito con
Cosa Res[MAXN];

5

Grazie così funziona :relieved: ho fatto 100/100, l’ho risolto con le strutture, speravo che si potesse fare anche senza, non mi sono mai messo a impararle come si deve :sweat_smile: