Ristorante 70/100 Testcase errato 17

[Ico456bart]

Non riesco a spiegarmi il motivo per cui tutti test vanno bene tranne il 17, che mi da output errato.

Questo è l’algoritmo:

#include <stdio.h>

void quicksort(int a[10000],int primo,int ultimo){
   int i, j, pivot, temp;
   if(primo<ultimo){
      pivot=primo;
      i=primo;
      j=ultimo;     
      while(i<j){
         while(a[i]<=a[pivot]&&i<ultimo)
            i++;
         while(a[j]>a[pivot])
            j--;
         if(i<j){   
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
         }
      }
      temp=a[pivot];
      a[pivot]=a[j];
      a[j]=temp;
      quicksort(a,primo,j-1);
      quicksort(a,j+1,ultimo);
   }
}

int main()
{
  FILE *fr=fopen("input.txt", "r");
  FILE *fw=fopen("output.txt", "w");
  
  int N, D, M, a[100000], k, sum=0;
  fscanf(fr, "%i %i", &N, &D);
  for(k=0; k<N; k++)
  {
    fscanf(fr, "%i", &a[k]);
    sum=sum+a[k];
  }
  fscanf(fr, "%i", &M);
  if(M>N)
  {
	int y;
	y=(M-N)*D;
	sum=sum-y;
	fprintf(fw, "%i", sum);
  }
  else if(M<N)
  {
    sum=0;
	quicksort(a, 0, N);
	for(int g=1; g<=M; g++)
	{
	  sum=sum+a[g];
	}
    fprintf(fw, "%i", sum);
  }
  else if(M==N)
  {
    fprintf(fw, "%i", sum);
  }
  fclose(fr);
  fclose(fw);
  return 0;
}

[simpatine]

Ciao!
Il problema è nel fatto che il vettore a[] è dichiarato localmente (all’interno della funzione main), questo non garantisce che i valori di a siano inizializzati a 0; inoltre la dimensione di a deve essere maggiore, infatti quando si richiama quicksort(a, 0, N); ci si può riferire ad un range di valori pari a 100001 (N-0+1);
Il mio consiglio è quello di inizializzare il più possibile le variabili globalmente, considerare le assunzioni dei problemi leggermente maggiori, ma soprattutto di non implementarsi mai funzioni come il quick sort , infatti esiste la funzione sort() già implementata nella libreria algorithm di c++ (che è inoltre ben più efficiente di qualsiasi sort implementabile in breve tempo).
Se inoltre può interessare non c’è bisogno che i primi M numeri siano correttamente ordinati, la funzione nth_element() potrebbe fare al caso tuo (il vantaggio sta nella complessità computazionale O(NlogN) per la sort() e O(N) per la nth_element() ).

[Ico456bart]

Avevi ragione, andava inizializzato globalmente il vettore a[] .
Grazie mille