C#

Нужно написать код на C#

Имея n неотрицательных целых чисел, представляющих карту высот, где ширина каждой полосы равна 1, вычислите, сколько воды она может собрать после дождя.

Например:

Ввод: высота = [4,2,0,3,2,5]

Выход: 9
using System;
class New_Project
{ static void Main()
{ uint i, n, sbor = 0; Console.Write("n: ");
n = uint.Parse(Console.ReadLine());
uint [] A = new uint [n];
Console.WriteLine("Heights: ");
var s = Console.ReadLine().Split(" ");
A[0] = uint.Parse(s[0]);
for (i = 1; i < n; i++)
{ A[i] = uint.Parse(s[i]);
sbor += Math.Min(A[i], A[i - 1]); }
Console.WriteLine("Сбор воды " + sbor); } }
Евгений Баханович
Евгений Баханович
66 572
Лучший ответ
Владимир Волотка На входные данные из вопроса ваш алгоритм вернёт 6, а не 9.
А кто это "она"? Карта, что-ли, или, быть может, ширина? ☺ Ё-маё, ну и задача!
Если система неизолирована от прочих высот, то есть слева от высоты 4 и/или справа от высоты 5 могут находиться другие высоты, то сбор может быть любым, но в таком случае можно переформулировать вопрос таким образом: какой может быть минимальный сбор воды в данной конкретной системе, если вода там вообще когда-нибудь появится и при учёте того, что вокруг избранной системы высот могут быть любые другие высоты? А о максимальном сборе придётся только догадываться...
А вот если точно известно, что система изолирована, тогда совсем другое дело - это хорошая алгоритмическая задача, по смыслу совпадающая с переформулированным вопросом. Но программу кодить я не буду, хотя бы потому что здесь нужна не столько программа, сколько алгоритм решения этой задачи, описанный в точных терминах достаточно простыми словами.
Mirtofik Qambarov
Mirtofik Qambarov
28 648
Евгений Баханович Виктор, по-моему, "она" -это, по-моему, всё таки, наверное, система высот. Если эта система изолирована, то воде просто некуда стекать за пределы этой изолированной системы. И тогда в таком, например, случае:
n: 5
1 6 5 4 3
какой по-Вашему будет сбор? Максимального сбора здесь вроде быть не может, а минимальный в любом случае будет таким:
n•max(i=1;n)A[i] - Σ(k=1;n)A[i].
Для приведённого примера минимальный сбор составит 11, да и то только если дождь ливанёт как следует и воды при этом не окажется едва чуть-чуть на донышке.
Если же система неизолирована, то всё зависит от сопредельных высот, а каковы они -неизвестно! Поэтому я и написала FF'y, что не вижу тут системы как таковой -с чёткими характеристиками и с правильным методом подсчёта возможного сбора дождя.
Евгений Баханович Мне, однако, понравилось, что FF переделал мою программу как счёл нужным, но его якобы "правильный ответ" совершенно не соответствует условиям задачи, как, впрочем, и мой собственный, но я вовсе не считаю свой ответ лучшим! А ответ FF'a вроде бы соответствует тому случаю, когда возможен бесконечный отток воды из рассматриваемой системы, то есть как если бы она была окружена с обоих сторон бесконечно глубокими пропастями, в которые вся вода, неспособная удержаться системой, утекала бы как в тартарары. Если Екатерина проверит ответ FF'a на серии тестов и все результаты её удовлетворят, тогда она его ответ просто может признать лучшим (если, конечно, ей баллов для этого хватит), а я так даже его ответу и плюс не поставила, и не собираюсь, потому что на мой взгляд он просто этого не достоин...
А теперь правильный ответ.
Ввод-вывод модифицируйте, как вам надо.

using System;
class Program
{
static void Main()
{
Console.Write("n: ");
int n = int.Parse(Console.ReadLine());

int[] A = new int[n];
int[] B = new int[n];
Console.WriteLine("Heights: ");
var s = Console.ReadLine().Split(',');

int max = 0;
for (int i = 0; i < n; i++)
{
A[i] = int.Parse(s[i]);
max = Math.Max(max, A[i]);
B[i] = max;
}

max = 0;
int sbor = 0;
for (int i = n - 1; i > 0; i--)
{
max = Math.Max(max, A[i]);
B[i] = Math.Min(max, B[i]);
sbor += B[i] - A[i];
}

Console.WriteLine("==> " + sbor);
Console.ReadLine();
}
}
Берик Казах
Берик Казах
5 779
Круто