x, y, z

Двумерный дождь

# 21 Июн 2018 16:12:04
Math

Игра происходит в двумерном мире, который состоит из блоков размером 1×1. Остров игрока представляет собой набор столбцов различной высоты, состоящих из блоков камня и окруженный морем. Над островом прошёл сильный дождь, который заполнил водой все низины, а не поместившаяся в них вода стекла в море, не увеличив его уровень. Придумайте алгоритм, который по заданному ландшафту острова определяет, сколько блоков воды осталось после дождя в низинах на острове.

Пример:
Высоты столбцов: 2, 5, 2, 3, 6, 9, 3, 1, 3, 4, 6.
Количество воды: 18.

Пример соответствует рисунку. Черным цветом обозначен камень, серым — вода
Пример соответствует рисунку. Черным цветом обозначен камень, серым — вода
# 27 Июл 2021 09:41:16
fwefw34
#include <iostream>

using namespace std;

int a(int s[], int i1, int i2)
{
int m = -1;
int v = 0;
int c = 0;
int x;
if (i1 < i2) {
for (int i = i1; i <= i2; ++i)
{
x = s[i];
if (x >= m) {
m = x;
c = 0;
} else {
v += (m - x);
++c;
}
}
} else {
for (int i = i1; i >= i2; --i)
{
x = s[i];
if (x >= m) {
m = x;
c = 0;
} else {
v += (m - x);
++c;
}
}
}
if (x < m) {
v -= c * (m - x);
}
return v;
}

int main()
{
int x, n, mm = -1, ii=0;
cin >> n;
int *arr = new int[n];
for (int i=0; i<n; ++i)
{
cin >> x;
arr[i] = x;
if (x > mm) {
mm = x;
ii = i;
}
}
cout << a(arr, 0, ii) + a(arr, n-1, ii);
}
*Имя:
Заголовок:
[tex-clear] [tex-help] [ted]
  • formulas >

* Вычислите
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.