Имея n неотрицательных целых чисел, представляющих карту высот, где ширина каждой полосы равна 1, вычислите, сколько воды она может собрать после дождя.
Например:
Ввод: высота = [4,2,0,3,2,5]
Выход: 9
C#
Нужно написать код на C#
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); } }
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); } }
Владимир Волотка
На входные данные из вопроса ваш алгоритм вернёт 6, а не 9.
А кто это "она"? Карта, что-ли, или, быть может, ширина? ☺ Ё-маё, ну и задача!
Если система неизолирована от прочих высот, то есть слева от высоты 4 и/или справа от высоты 5 могут находиться другие высоты, то сбор может быть любым, но в таком случае можно переформулировать вопрос таким образом: какой может быть минимальный сбор воды в данной конкретной системе, если вода там вообще когда-нибудь появится и при учёте того, что вокруг избранной системы высот могут быть любые другие высоты? А о максимальном сборе придётся только догадываться...
А вот если точно известно, что система изолирована, тогда совсем другое дело - это хорошая алгоритмическая задача, по смыслу совпадающая с переформулированным вопросом. Но программу кодить я не буду, хотя бы потому что здесь нужна не столько программа, сколько алгоритм решения этой задачи, описанный в точных терминах достаточно простыми словами.
Если система неизолирована от прочих высот, то есть слева от высоты 4 и/или справа от высоты 5 могут находиться другие высоты, то сбор может быть любым, но в таком случае можно переформулировать вопрос таким образом: какой может быть минимальный сбор воды в данной конкретной системе, если вода там вообще когда-нибудь появится и при учёте того, что вокруг избранной системы высот могут быть любые другие высоты? А о максимальном сборе придётся только догадываться...
А вот если точно известно, что система изолирована, тогда совсем другое дело - это хорошая алгоритмическая задача, по смыслу совпадающая с переформулированным вопросом. Но программу кодить я не буду, хотя бы потому что здесь нужна не столько программа, сколько алгоритм решения этой задачи, описанный в точных терминах достаточно простыми словами.
Евгений Баханович
Виктор, по-моему, "она" -это, по-моему, всё таки, наверное, система высот. Если эта система изолирована, то воде просто некуда стекать за пределы этой изолированной системы. И тогда в таком, например, случае:
n: 5
1 6 5 4 3
какой по-Вашему будет сбор? Максимального сбора здесь вроде быть не может, а минимальный в любом случае будет таким:
n•max(i=1;n)A[i] - Σ(k=1;n)A[i].
Для приведённого примера минимальный сбор составит 11, да и то только если дождь ливанёт как следует и воды при этом не окажется едва чуть-чуть на донышке.
Если же система неизолирована, то всё зависит от сопредельных высот, а каковы они -неизвестно! Поэтому я и написала FF'y, что не вижу тут системы как таковой -с чёткими характеристиками и с правильным методом подсчёта возможного сбора дождя.
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();
}
}
Ввод-вывод модифицируйте, как вам надо.
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();
}
}
Круто
Похожие вопросы
- Зачем разбивать код в C# на отдельные классы?
- Помогите исправить код на C#
- Написать программу на C# вычисления стоимости покупки с учетом скидки.
- Помогите написать программу на C# По задачнику PascalABC Case20
- Помогите написать задачу на C#
- Как написать код? unity 2d
- Помогите с кодом C#!!
- Почему C# относится к компилируемым языкам, компиляция это перевод всего кода в машинный, а C# переводится в байт код
- C#: помогите, пожалуйста, исправить код
- DI C# как понять? Что это такое? Как в коде писать? Простыми словами обьясните зависимости эти А то везде сложно пишут