# Ristorante 70/100 Testcase errato 17

**URL:** <https://forum.olinfo.it/t/ristorante-70-100-testcase-errato-17/5944>\
**Category:** Aiuto\
**Created:** [27 Novembre 2019, 5:44pm UTC](https://forum.olinfo.it/t/ristorante-70-100-testcase-errato-17/5944 "2019-11-27T17:44:15Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\
**Post date:** [27 Novembre 2019, 5:44pm UTC](https://forum.olinfo.it/t/ristorante-70-100-testcase-errato-17/5944/1 "2019-11-27T17:44:15Z")

</div>

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

Questo è l’algoritmo:

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [27 Novembre 2019, 9:49pm UTC](https://forum.olinfo.it/t/ristorante-70-100-testcase-errato-17/5944/2 "2019-11-27T21:49:41Z")

</div>

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()](http://www.cplusplus.com/reference/algorithm/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()](http://www.cplusplus.com/reference/algorithm/nth_element/?kw=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() ).

---

<div class="post-metadata">

**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\
**Post date:** [28 Novembre 2019, 2:35pm UTC](https://forum.olinfo.it/t/ristorante-70-100-testcase-errato-17/5944/3 "2019-11-28T14:35:59Z")

</div>

Avevi ragione, andava inizializzato globalmente il vettore a[] 🤦‍♂️😅.  
Grazie mille 👍