Solução por Lúcio Cardoso
Vamos descobrir o primeiro capítulo que não foi lido totalmente, ou seja, o capítulo que contém a página $$k$$. Se o capítulo $$i$$ contém a página $$k$$, então $$l_i \leq k$$ e $$k \leq r_i$$, ou seja, $$k$$ está entre $$l_i$$ e $$r_i$$. Assim, para encontrar o primeiro capítulo não lido, basta testar a condição acima em cada um dos capítulos e quando for verdadeira, guardamos o índice do capítulo em uma variável $$ind$$. Assim, a resposta será $$N-ind+1$$ (quantidade de capítulos desde $$ind$$ até $$N$$). A complexidade será então $$O(n)$$.
Confira o código abaixo 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
| // Noic – Iniciante – Semana 50 – Problema 1 | |
| // O(n) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 110; | |
| int l[maxn], r[maxn]; | |
| int main(void) | |
| { | |
| int n, k; | |
| cin >> n; | |
| for (int i = 1; i <= n; i++) | |
| cin >> l[i] >> r[i]; | |
| cin >> k; | |
| int ind; // capítulo que contém k | |
| for (int i = 1; i <= n; i++) | |
| if (l[i] <= k && k <= r[i]) | |
| ind = i; | |
| cout << n-ind+1 << "\n"; | |
| } |
Comente