Vetores

Aula de Rogério Junior

Imagine um problema bem simples: imprimir uma sequência de números de trás para frente. A entrada consiste de duas linha. Na primeira, haverá um inteiro n (\(1\leq\)n\(\leq 10^6\)) e, na segunda, um sequência de n números inteiros separados por um espaço em branco. A saída deve gerar uma única linha: Os n números da sequência lida, mas impressos de trás para frente (do último para o primeiro).

Você já deve ter percebido que vamos precisar salvar esses números, visto que não poderemos imprimi-los na ordem em que aparecem. Porém, como declarar n variáveis se não conheço o valor de n? Criando um vetor de números inteiros. Um vetor (ou um array, são sinônimos) é uma sequência de variáveis em que podemos acessá-las pelo índice.

Para criar um vetor, escrevo seu tipo, seu nome, e, em seguida, quantas variáveis ele vai guardar, entre colchetes []. Para declarar um vetor de inteiros com o nome sequencia para guardar 10 posições, por exemplo, escreveria o comando: int sequencia[10];. Assim, o computador separa, na sua memória, o espaço para armazenar 10 inteiros. Para me referir ao elemento de índice 5 deste vetor, por exemplo imprimí-lo, eu o chamaria pelo índice, escrevendo cout<<sequencia[5];. Para ler um número na tela e guardá-lo no índice 5 do vetor, faria um comando análogo: cin>>sequencia[5];. Vale lembrar que, como mostrado na figura acima, se o vetor tem n posições, ele estará indexado de 0 a n-1, ou seja, o primeiro elemento será o sequencia[0], o segundo será o sequencia[1] e o último será o sequencia[n-1]. No caso, como declaramos um vetor de 10 posições, teremos os índices de 0 té 9.

Quando já sabemos todos os elementos do vetor na hora da sua inicialização podemos informar esses elementos já na declaração do vetor, através do comando ={}. Escrever, por exemplo, int vetor[5]={0, 1, 4, 8, 16}; significa declarar um vetor de inteiros de 5 posições cujo nome é vetor e, onde a posição 0 do vetor receberá 0, a posição 1 receberá 1, a 2 receberá 4,  a 3 receberá 8 e a 4 receberá 16.

Geralmente usamos um for para percorrer todas as casas do vetor, fazendo um inteiro i ser o índice que queremos acessar e fazemos ele variar entre as posições do vetor que desejo percorrer. Agora ficou fácil fazer o problema do início, não? Vamos declarar um vetor de 1000010 posições, (pois \(10^6\) é o valor máximo de n e quando declaramos vetores estáticos dessa forma, sempre adicionamos uma sobra) e, usando um for que irá de 0 até n-1, vou salvar os números lidos na tela nas posições de 0 a n-1. Feito isso usaremos um for que vai de n-1 até 0 para percorrer o vetor de trás para frente e imprimir cada número no vetor. Vamos ao código:


#include <iostream> // cin e cout

using namespace std;
 
int main(){
  
  int n; // declaro a variável n
  int sequencia[1000010]; // declaro o vetor de inteiros "sequencia" de 1000010 posições
  
  cin>>n; // leio o valor de n na tela
  
  for(int i=0; i<n; i++){
    cin>>sequencia[i]; // salvo cada número em uma posição do vetor, de 0 até n-1
  }
  
  for(int i=n-1; i>=0; i--){
    cout<<sequencia[i]<<" "; // percorro o vetor de trás para frente, imprimindo seus elementos
  }
  
  cout<<"\n"; // imprimo a quebra de linha ao fim do código
  
  return 0;
}

Agora que você já sabe fazer o básico de vetores, tente fazer o problema Sub-Prime. Se  não conseguir, segue a solução comentada abaixo abaixo, mas realmente tente resolvê-lo antes de lê-la!

O uso de vetor neste caso será para guardarmos o fundo monetário que cada banco possui. No começo, vamos declarar um vetor de nome fundo de 21 posições, pois são no máximo 20 bancos e, no começo de cada caso de teste, salvaremos o fundo do banco de número i na posição i do vetor. Antes veja que usaremos o break para finalizar a leitura quando ocorrer o fim de entrada (nb forem zero). Agora que temos salvos os fundos de cada banco, vamos abrir um for que se repetirá n vezes e, a cada repetição, executará uma operação de debênture. No caso, essa operação consiste em ler os valores do banco devedor d, do credor c e do valor de transferência v, subtrair o valor de v do fundo do banco devedor ("fundo[d]-=v;") e adicionar este valor ao fundo do banco credor ("fundo[c]+=v;"). Após realizarmos todas as operações, vamos verificar se algum banco precisa de ajuda financeira. Vamos declarar uma variável ajuda que começará com o valor 0. Vamos usar um for para olharmos todas as posições do vetor fundo e, se em alguma delas o valor estiver negativo, significa que este banco terminou endividado e precisará de ajuda, logo ajuda receberá 1. Terminada a verificação, se o valor de ajuda ainda for zero, nenhum banco precisou de auxílio financeiro e então imprimiremos "S". Caso contrário, algum banco está com fundo negativo e precisará de dinheiro, e imprimiremos "N". Segue o código:


#include <iostream> // cin e cout

using namespace std;

int main(){
  
  int b, n; // declaro as variáveis b e n
  
  int fundo[21]; // declaro o vetor de inteiros "fundo" com 21 posições, que guardará o dinheiros dos bancos
  
  while(true){ // repita o loop enquando "a verdade for verdade", ou seja, até que o laço seja parado por um comando break
    
    cin>>b>>n; // leia os valores de b e n
    
    if(b==0 && n==0){
      break; // se b e n forem ambos zero, termine o loop
    }
    
    for(int i=1; i<=b; i++){
      cin>>fundo[i]; // leia o valor do fundo de cada banco
    }
    
    for(int i=1; i<=n; i++){ // para cada operação de debênture
      
      int d, c, v; // declare as variáveis inteiras d, c e b
      cin>>d>>c>>v; // leia os valores de "d", "c" e "v".
      
      fundo[d]-=v; // tire do fundo do banco devedor o valor da transferência
      fundo[c]+=v; // e adicione este valor ao fundo do banco credor
    }
    
    int ajuda=0; // declare a variável ajuda, inicializada com o valor zero
    
    for(int i=1; i<=b; i++){
      if(fundo[i]<0){
        ajuda=1; // se algum banco tiver fundo negativo, ajuda receberá 1
      } 
    }
    
    if(ajuda==0){
      cout<<"S\n"; // se ajuda for zero, é possível tudo ser pago sem ajuda do governo
    }else{
      cout<<"N\n"; // caso contrário, o banco central deverá ajudar algum banco
    }
  }
   
  return 0;
}