Решение задачи "Элитные дома" с Codeforces

Без пояснения   Просмотров: 9

В столице Берляндии есть n многоэтажных домов. Архитектор, который застраивал столицу, был человеком очень творческим, поэтому все дома были построены в один ряд.

Пронумеруем все дома слева направо, начиная с единицы. Дом считается элитным, если количество этажей в нем строго больше, чем во всех домах с большими номерами. Иными словами, дом элитный, если количество этажей в нем строго больше, чем во всех домах, которые расположены правее, чем он. В данной задаче полагается, что высоты всех этажей во всех домах одинаковы.

Нового архитектора заинтересовали n вопросов, i-й из которых звучит так: «сколько этажей нужно достроить к i-му дому, чтобы он стал элитным?» (где i принимает все значения от 1 до n). Вам предстоит помочь ему справиться с этой задачей.

Заметим, что все вопросы независимы друг от друга — ответ на вопрос для дома i не влияет на другие ответы (то есть, этажи к домам на самом деле не достраиваются).

Код 

#include<bits/stdc++.h>
using namespace std;
int n,h[200000],a[200000];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>h[i];
	for(int i=n-1;i>=0;i--)
		a[i]=max(a[i+1],h[i+1]);
	for(int i=0;i<n;i++)
		cout<<max(a[i]-h[i]+1,0)<<' ';
	return 0;
}

         

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


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

Комментарии

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