Divisió Equilibrada. X15648

Sigui v un vector d’enters de mida $n > 2$. Una divisió de v és una posició $i$ del vector (on $0 \leq i \leq n-1$), tal que divideix el vector v en dues parts:

• les posicions que van del $0$ a $i-1$.

• les posicions que van de $i$ fins a $n-1$.

La divisió equilibrada és una posició $i$ de la llista tal que diferència entre la suma dels elements que hi ha des de la posició $0$ fins a la posició $i-1$ i la suma dels elements entre les posicions $i$ i $n-1$ és mínima.

Feu la funció :

int divisio_equilibrada(const vector<int>& v){

// Pre: v es un vector d'enters no buit de mida n > 2

// Post: Retorna la posició corresponent a la partició equilibrada

// Si n'hi haguessin més d'una retorna la de més a l'esquerra

Per exemple, si la funció rep el vector:

• $v = [4 , 1 , 2 , 3]$, retorna $2$, ja que $(4 + 1) - (2 + 3) = 0$ que és la diferència mínima

• $v = [2 , 1 , -3, 4]$, retorna $1$, ja que $(2) - (1 - 3 + 4) = 0$ que és la diferència mínima

Tingueu en compte que, si calculeu la suma total de la llista al principi de la funció, podreu resoldre aquest problema amb una sola passada sobre el vector v. La primera vegada la suma de l’esquerra valdrà $0$ i la suma de la dreta serà la suma de tots els elements. A partir d’aquí podeu pasar un element de la dreta a l’esquerra a cada passada.

Després heu de fer un programa principal que llegeixi una seqüència d’enters acabada en $0$, crei el vector amb tots els elements llegits menys el $0$, cridi a la funció anterior i mostri el resultat per pantalla

Entrada

Una seqüència d’enters acabada en $0$ de longitut $n > 2$.

Sortida

La divisió equilibrada del vector v creat amb la seqüència d’entrada. Si n’hi haguessin més d’una, torneu la de més a l’esquerra.