Solução por Rogério Júnior
Checar qual seção que divide igualmente o território de valor $$A$$ equivale a checar qual delas é tal que, somando-a a a todos os territórios anteriores a ela, obtemos exatamente $$\frac{A}{2}$$. Assim, vamos salvar o valores da entrada em um vetor $$secao$$ e a soma deles em uma variável $$A$$. Depois, declaramos uma variável $$soma$$, que será inicializada com o valor $$0$$, e adicionaremos a ela, um a um, o valor de cada um dos territórios armazenados em $$secao$$. Quando o valor de $$soma$$ for exatamente $$\frac{A}{2}$$, então imprimiremos na tela o índice que correspondente àquela seção. É importante lembrar, porém, que para checar essa igualdade, devemos fazer $$2*soma==A$$, pois, em C++, como $$A$$ e $$2$$ são inteiros, $$\frac{A}{2}$$ retorna $$\lfloor\frac{A}{2}\rfloor$$. Vamos ao código:
| #include <cstdio> // printf, scanf | |
| int secao[100100], A, soma, n; // declare o vetor secao e as variáveis A, soma e n | |
| int main(){ | |
| scanf("%d", &n); | |
| for(int i=1; i<=n; i++){ // leia a entrada | |
| scanf("%d", &secao[i]); // salve o valor de cada seção no vetor | |
| A+=secao[i]; // some o valor da seção atual a A para que, ao final da leitura da entrada, ela tenha o valor da soma de todos os territórios | |
| } | |
| for(int i=1; i<=n; i++){ // para cada índice do vetor | |
| soma+=secao[i]; // adicione seu valor a soma | |
| if(2*soma==A){ // cheque se a soma está valendo metade do território total | |
| printf("%d\n", i); // se sim, imprima o valor do índice em que isso ocorreu | |
| break; // e pare o loop | |
| } | |
| } | |
| return 0; | |
| } |
Abaixo, a solução, em Java, do leitor Roger Benet:
| import java.io.*; | |
| public class solucao{ | |
| public static void main(String[] args)throws IOException{ | |
| BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); | |
| BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); | |
| int[] vet = new int[110000]; | |
| int i,n,sm1,sm2; | |
| String[] aux; | |
| n = Integer.parseInt(in.readLine()); | |
| aux = in.readLine().split(" "); | |
| sm1 = 0; | |
| sm2 = 0; | |
| for(i = 0; i < n; i++){ | |
| vet[i] = Integer.parseInt(aux[i]); | |
| sm1 += vet[i]; | |
| } | |
| sm1 -= vet[i-1]; | |
| sm2 += vet[i-1]; | |
| for(i = n – 2; i > -1; i–){ | |
| if(sm1 == sm2){ | |
| out.write((i+1)+"\n"); | |
| break; | |
| } | |
| else { | |
| sm1 -= vet[i]; | |
| sm2 += vet[i]; | |
| } | |
| } | |
| out.flush(); | |
| } | |
| } |

Comente