Решение задачи Петя и деревня с Codeforces

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

Маленький Петя часто ездит к бабушке в деревню. У бабушки есть большой огород, который, если смотреть сверху, можно представить в виде прямоугольника размером 1 × n, разбитого на n одинаковых квадратных участков. Особенностью огорода является то, что каждый из квадратных участков имеет свою фиксированную высоту и над каждым из участков при помощи новейшей системы водоснабжения может быть создан искусственный дождь над этим участком.

Создание искусственного дождя — дорогостоящая операция, поэтому мы ограничимся тем, что искусственный дождь будет создан лишь над одним участком. При этом вода с каждого затопленного участка будет попадать на соседние с ним участки, если их высота не превосходит высоту данного участка. То есть, к примеру, если огород представляет собой прямоугольник 1 × 5, где высоты участков равны 4, 2, 3, 3, 2, то создав искусственный дождь над любым из участков с высотой 3 — вода разольется по всем участкам, кроме участка с высотой 4. Картинка, поясняющая этот пример:


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

Код 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,ans=0;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++){
		int cnt =1;
		for(int j=i-1;j>=0&&a[j]<=a[j+1];j--)cnt++;
		for(int j=i+1;j<n&&a[j]<=a[j-1];j++)cnt++;
		ans=max(ans,cnt);
	}
	cout<<ans;
    return 0;
}

         

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


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

Тут нужно перебрать все возможные позиции для создания искусственного дождя, посмотреть сколько в каждом из случаев получается участков, содержащих воду и выбрать среди всех возможных вариантов максимальный. При этом подсчитывать ответ для текущей позиции будем, просто расходясь вправо и влево от текущей позиции. Итоговая сложность O(N^2).



Комментарии

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


© 2020 HSECODES [email protected] Карта сайта