Solução por Rogério Júnior
Para ver o problema original, clique aqui.
Vamos salvar a sequência no array $$vetor$$, e depois ordená-lo. Vamos agora processar ordenadamente cada um dos números do vetor. Seja $$resp$$ o menor inteiro que não conseguimos formar com os elementos que já temos. Antes de processar qualquer elemento, o valor de $$resp$$ é $$1$$, pois não temos elementos para formá-lo.
Agora, para cada elemento, observe o processamento do $$i$$-ésimo elemento do array. Se $$resp$$ é o menor elemento que não podemos formar, então conseguimos formar todas as somas de $$1$$ a $$resp-1$$. Se $$vetor[i] > resp$$, então não há como formarmos o valor de $$resp$$ usando elemento anteriores a $$i$$ (por definição de $$resp$$) nem com elemento a partir de $$i$$ (pois serão todos maiores que $$resp$$). Logo não preciso mais processar o resto do vetor e a resposta é $$resp$$.
Entretanto, se $$vetor[i]<resp$$, consigo formar todos os valores de $$resp$$ a $$vetor[i]+resp-1$$, pois sendo $$s$$ uma soma qualquer, seja $$x=s-vetor[i]$$. Logo para utilizarmos $$vetor[i]$$ em um subconjunto a fim de obtermos soma $$s$$, precisamos formar $$x$$ com outros, e só conseguimos formar $$1 \leq x <resp \Rightarrow resp \leq s < resp+s$$. Logo, o novo valor de $$resp$$ é $$resp+vetor[i]$$ e partiremos para a análise do próximo elemento. Segue o código para melhor entendimento:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // URI – 1690 | |
| // Rogério Júnior | |
| // O(n log n) | |
| #include <cstdio> | |
| #include <algorithm> | |
| using namespace std; | |
| #define MAXN 10100 | |
| int t, n, vetor[MAXN]; | |
| int main(){ | |
| scanf("%d", &t); | |
| // para cada caso | |
| while(t–){ | |
| scanf("%d", &n); | |
| // salvo os números em vetor | |
| for(int i=0; i<n; i++) scanf("%d", &vetor[i]); | |
| // ordeno os elementos de vetor | |
| sort(vetor, vetor+n); | |
| // resp começa com 1 | |
| long long int resp=1; | |
| // para cada elemento | |
| for(int i=0; i<n; i++){ | |
| // se ele for maior que resp, não podemos formá-labs | |
| // e o algoritmo para | |
| if(vetor[i]>resp) break; | |
| // caso contrário, atualizamos o valor de resp | |
| else resp+=vetor[i]; | |
| } | |
| // no fim, imprimimos o valor de resp | |
| printf("%lld\n", resp); | |
| } | |
| return 0; | |
| } |
Comente