Решение задачи Детектив с Codeforces

С пояснением   Просмотров: 28

Недавно Иван купил очень интересный детектив. На каждой странице книги появляется какая-то тайна, разгадка которой находится где-то дальше по тексту. Формально, i-я страница содержит тайну, которая проясняется на странице ai (ai≥i).

Иван хочет прочесть всю книгу. Каждый день он читает первую из еще не прочитанных страниц и продолжает читать их подряд, пока не прояснятся все тайны, о которых он прочитал (Иван прекращает чтение, если не существует такой страницы i, что ее Иван прочитал, а ai — нет). После этого он закрывает книгу и откладывает чтение следующей страницы до завтра.

Сколько дней понадобится Ивану, чтобы прочесть всю книгу?

Код 

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n,x,maxi=0,ans=0,i,j;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x;
		maxi=max(x,maxi);
		if(maxi==i)
			ans++;
	}
	cout<<ans;
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Решение — это просто реализация: воспроизведите алгоритм, заданный в условии, поддерживая максимум на префиксе a[i], и останавливаясь, когда максимум становится меньше номера следующей страницы.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES bminhojkhon03@gmail.com Карта сайта