Solução por Sofhia de Souza
Esse problema é facilmente resolvido com um algoritmo guloso. A ideia é a seguinte: sabemos que, para formarmos um triângulo, suas extremidades têm que começar com altura 1 e ir crescendo de 1 em 1, certo? Usaremos então esse conceito ao nosso favor, para que possamos limitar as alturas que cada coluna pode usar em um triângulo. Primeiro, limitaremos a extremidade esquerda do muro: colocaremos a primeira como 1, a segunda como 2, e assim por diante (enquanto as alturas dessas colunas permitirem). Se a altura que queremos (a altura anterior + 1) for maior que a altura da coluna, colocamos a própria altura da coluna e continuamos normalmente com o algoritmo. Depois, com esse vetor atualizado, faremos a mesma coisa com a extremidade direita.
Simulemos isso com o seguinte exemplo : 5 4 9 3 2. Sabemos que a primeira coluna pode ter altura no máximo 1, pois não possui mais nenhuma coluna pra esquerda, certo? Logo, agora nosso vetor é 1 4 9 3 2. Agora, a segunda coluna, ela pode ser no máximo 2, pois sua coluna anterior é no máximo 1. Então, nosso vetor agora se torna 1 2 9 3 2. Faremos o mesmo para as últimas 3 colunas, e terminaremos com o vetor igual a 1 2 3 3 2. Agora, aplicaremos o mesmo algoritmo, de trás pra frente no vetor. Temos que a coluna 5 pode ser no máximo 1, pois não possui mais nenhuma coluna a sua direita. Ficamos então com o vetor 1 2 3 3 1. A quarta coluna pode ser no máximo 2, pois a coluna a sua direita pode ser no máximo 1. Ficamos com 1 2 3 2 1. Fazemos a mesma coisa com as 3 colunas que faltam, e terminamos com o vetor 1 2 3 2 1. Assim, a resposta será a maior altura que aparece no vetor, nesse caso, 3.
Segue o código para melhor entendimento:
This file contains 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
| //Isósceles - 2243 URI | |
| //Sofhia de Souza Gonçalves | |
| #include <bits/stdc++.h> | |
| #define MAXN 50010 | |
| using namespace std; | |
| int main() | |
| { | |
| int n, vet[MAXN]; | |
| scanf("%d", &n); | |
| for(int i = 1 ; i <= n ; i++) | |
| scanf("%d", &vet[i]); //leio os valores das alturas | |
| vet[1] = 1; | |
| for(int i = 2 ; i <= n ; i++) | |
| vet[i] = min(vet[i-1]+1, vet[i]); //atualizo o valor de vet[i] pro maior valor possivel pra ele, respeitando os limites da esquerda | |
| vet[n] = 1; | |
| int maior = 1; | |
| for(int i = n-1 ; i >= 1 ; i--) | |
| { | |
| vet[i] = min(vet[i+1]+1, vet[i]); //atualizo o valor de vet[i] pro maior valor possivel pra ele, respeitando os limites da direita | |
| maior = max(vet[i], maior); //se vet[i] for maior que o maior atual, atualizo o valor do maior | |
| } | |
| printf("%d\n", maior); //imprimo o maior | |
| } |