Problema A - Clube de leitura

O Problema

Dados os $N$ livros que constituem o stock da Dona Alexandra e o número de pontos $Z$ que a Zbox vale, devolve o número de livros que o Gabriel tem de ler para receber o prémio.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 3 grupos com restrições adicionais diferentes:

Solução Base

Neste problema pedem-nos para calcular o número de livros que são necessários ler de tal forma a que os livros sejam lidos por ordem crescente de número de páginas e o total de páginas lidas seja maior que um $Z$ dado.

A solução mais simples é, de cada vez que temos de escolher um livro novo para ler, percorrer a lista toda e escolher o menor livro ainda não lido, somando a sua pontuação a um contador e marcando o livro como lido (para evitar repetições). O código para tal seria algo como:

#include <stdio.h>

int livros[100005]; // paginas dos livros
int usado[100005]; // livros que ja lemos

int main() {
  int n, z;
  scanf("%d %d", &n, &z);

  for (int i = 0; i < n; i++) {
    scanf("%d", &livros[i]);
    usado[i] = 0; // inicialmente nao lemos nenhum
  }

  int soma = 0, i, j;
  for (livros_necessarios = 0; livros_necessarios < n; livros_necessarios++) {
    int livro_ler = 2000000; // paginas do menor livro ainda nao lido
    int indice_ler = 0; // indice do menor livro nao lido
    for (j = 0; j < n; j++) {
      if (!usado[j] && livros[j] < livro_ler) { // se ainda nao lemos e e menor
        livro_ler = livros[j];
        indice_ler = i;
      }
    }

    soma += livro_ler; // atualizamos a soma
    usado[i] = 1;
    
    if (soma >= z) // ja podemos comprar a zbox
       break;
  }
  
  printf("%d\n", livros_necessarios); // imprimir a resposta

  return 0;
}

Para sabermos quantos pontos é que esta solução daria, temos de calcular o número de operações que um programa que a execute faz. Este tipo de procedimento chama-se "Análise de Algoritmos" ou "Análise da Complexidade Algoritmos", que são apenas termos engraçados para dizer "quantas operações é que o nosso algoritmo faz". Para uma introdução detalhada a este tema podem consultar o seguinte artigo do Loop:

Artigo: Introdução à Análise de Algoritmos

Este artigo contém uma introdução a análise de algoritmos.

Vamos às contas: por cada novo livro que pretendemos, podemos ter de percorrer os $N$ livros para encontrar o menor que ainda não usámos. Visto que podemos pretender os $N$ livros e para cada livro podemos ter que percorrer os $N$ livros, podemos ter que executar cerca de $N^2$ operações no total. Na notação que vimos no artigo a cima, isto significa que o algoritmo tem uma complexidade temporal de $O(N^2)$. Usando as tabelas no artigo, vemos que um algoritmo com complexidade assim só demora menos de um segundo (o tempo limite do problema) se $N$ for menor que cerca de 10.000 ou 1.000, ou seja, esta solução daria apenas aproximadamente 60 pontos, equivalentes aos primeiros dois grupos.

Solução Ótima

Para melhorar esta solução podemos observar que estamos a fazer muito trabalho repetido sempre que pretendemos um novo livro. Será que temos de percorrer a lista toda de livros sempre que pretendemos um novo livro? Reparem que trabalho repetido significa que o nosso programa vai ser mais lento desnecessariamente e por isso obter menos pontos.

Imaginem que a lista de livros estava ordenada por número de páginas por ordem crescente. Assim, sempre que pretendessemos o livro seguinte sabiamos exatamente qual: é o livro que sucede ao livro que lemos anteriormente na lista ordenada. Assim, só temos de percorrer a lista ordenada de livros um a um, somando o seu número de páginas, parando quando a soma excede ou iguala $Z$. Isto só necessitava de uma operação de somar por livro, ou seja, a solução usaria no total cerca de $N$ operações, isto é, teria complexidade $O(N)$, o que já seria suficiente para a pontuação completa.

Infelizmente os livros não vêm ordenados, por isso temos de os ordenar. Ordenar uma lista de números é uma operação clássica em concursos de programação, é talvez o primeiro algoritmo importante que devem aprender. Se pensarem em como ordenar um baralho de cartas um método que normalmente usamos e que podemos adaptar para um programa seria: pegamos no baralho desorganizado, procuramos a carta mais baixa ao passar por todas as cartas, colocamos numa nova pilha de cartas e repetimos até encontrarmos todas as cartas. Se repararem, este método é exatamente o que fizémos na solução base anterior, ou seja, vai ter uma complexidade $O(N^2)$ na mesma. A nossa sorte é que o problema de ordenar um conjunto de números pode ser resolvido com complexidade temporal $O(N \log(N))$ de várias formas. Infelizmente o Loop ainda não contém um artigo sobre ordenação (terá em breve), por isso podem consultar os seguintes links para aprenderem sobre dois algoritmos de ordenação diferentes que têm complexidade temporal $O(N \log(N))$: quick sort e merge sort. De facto, tanto o C/C++ como o Java têm funções já implementadas que ordenam uma lista de números: qsort no caso do C; sort no caso do C++; Arrays.sort no caso do Java.

Combinando ambas as ideias, obtemos um algoritmo de complexidade $O(N + N \log(N))$ que, se se recordarem de como funciona a notação $O()$, é equivalente a $O(N \log(N))$, o que seria suficiente para os 100 pontos.