Минимальное количество команд для исполнителя МГППНВ

@Kakjit · Регистрация: 11.11.2017

Author24 — интернет-сервис помощи студентам

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

@OwenGlendower · 11.11.2017, 18:53

Комментарий модератора

Читаем правила форума:

5.18 Запрещено размещать задания и решения в виде картинок и других файлов с их текстом.

@Kakjit · 11.11.2017, 21:00 **[ТС]**

Извиняюсь, вот задание
Инженеры придумали изобретение, решающее эту проблему - Магнитно-глицериновую программируемую пушку направленного взрыва (МГППНВ). Исполнитель для МГППНВ имеет две команды:
1) Создать направленный взрыв, разрушающий конкретный дом без последствий для соседних домов.
2) Создать направленный взрыв, разрушающий у всех домов X-ый этаж. При этом, если дом этажностью больше X, то все этажи выше X "падают" на один этаж ниже.
К сожалению, специалисты КРСК не умеют обращаться правильно с исполнителем для МГППНВ. Но они точно знают, что время - деньги, поэтому хотят снести квартал за минимальное число команд. И они обратились к вам за помощью!
Формат ввода:

Входный данные состоят из двух строк.
В первой строке содержится N - число домов в квартале (2 ≤ N ≤ 105). Вторая строка содержит N чисел hi - высоты домов (1 ≤ hi ≤ 106).

Выведите единственное число - минимальное количество команд для исполнителя, после которого гарантирован снос квартала.

Ввод
6
2 1 8 8 2 3
Вывод
5
Ввод
1 1 1 1 10
Вывод
2

Добавлено через 2 часа 1 минуту
Вроде написала, но по времени не проходит, что тут можно ускорить, подскажите пожалуйста

C#

for (int i = 0; i <= arr.Length - 1; i++)
            {
                if (arr[i] == arr[arr.Length - 1] || arr[i] != arr[i + 1])
                {
                    int current_Index = Array.BinarySearch(arr, arr[i]);
                    for (int j = current_Index; j < arr.Length; j++)
                    {
                        if (arr[i] == arr[j])
                        {
                            count1++;
                        }
                    }
                    for (int j = current_Index - 1; j >= 0; j--)
                    {
                        if (arr[i] == arr[j])
                        {
                            count1++;
                        }
                    }
 
                    if (arr[i] > count1)
                    {
                        count += count1;
                    }
                    else if (arr[i] < count1)
                    {
                        count += arr[i];
                    }
                    else if (arr[i] == count)
                    {
                        count++;
                    }
                    count1 = 0;
                }

@Diamante · 12.11.2017, 00:42

Сообщение от Kakjit

что тут можно ускорить, подскажите пожалуйста

свои мысли есть?
что можно использовать? только массивы? что еще из базового функционала шарпа допускается?

@Kakjit · 12.11.2017, 02:14 **[ТС]**

Да все можно использовать, нет ограничений, как таковых
Толковых мыслей нет, поэтому и пришла сюда, увы

Добавлено через 38 минут
Но ответ все равно на 1 меньше выводит нужного, не знаю в чем дело

C#

for (int i = 0; i <= arr.Length - 1; i++)
            {
                if (arr[i] == arr[arr.Length - 1] || arr[i] != arr[i + 1])
                {
                    int current_Index = Array.BinarySearch(arr, arr[i]);
                    for (int j = current_Index; j < arr.Length; j++)
                    {
                        if (arr[i] == arr[j])
                        {
                            count1++; // вот в этот цикл дописать надо будет еще else break;
                        }
                    }
                    for (int j = current_Index - 1; j >= 0; j--)
                    {
                        if (arr[i] == arr[j])
                        {
                            count1++; // вот в этом еще тоже else break
                        }
                    }
 
                    if (arr[i] > count1)
                    {
                        count += count1;
                    }
                    else if (arr[i] < count1)
                    {
                        count += arr[i];
                    }
                    else if (arr[i] == count)
                    {
                        count++;
                    }
                    count1 = 0;
                }

@Aael · 12.11.2017, 09:25

Kakjit, располагаем дома по убыванию числа этажей. Предполагаем, что командой 1 взорвали первые n домов (самые большие), значит вторую команду нужно применить h[n+1] раз (число этажей в самом большом оставшемся доме). Ищем минимум среди чисел n+h[n+1].

C#

1
2
3

var h = new int[]{ 2, 1, 8, 8, 2, 3, 0}; // важно добавить ноль
var r = h.OrderByDescending(x => x).Select((x, i) => x + i).Min();
Console.WriteLine(r);

@Kakjit · 12.11.2017, 10:49 **[ТС]**

Обалдеть, в две строки, хотела бы я так же программировать)
Спасибо Вам!

@Kakjit 0 / 0 / 0 Регистрация: 11.11.2017 Сообщений: 4
		1
	.NET 4.x Минимальное количество команд для исполнителя МГППНВ 11.11.2017, 18:30. Показов 1374. Ответов 6 Метки нет (Все метки) Здравствуйте, помогите пожалуйста с задачей, можно даже без кода, просто с алгоритмом решения, пыталась сама, ничего не вышло.Заранее спасибо 0

@Diamante 3564 / 2505 / 1174 Регистрация: 14.08.2016 Сообщений: 8,211
	12.11.2017, 00:42	4
	Сообщение от Kakjit что тут можно ускорить, подскажите пожалуйста свои мысли есть? что можно использовать? только массивы? что еще из базового функционала шарпа допускается? 0

@Kakjit 0 / 0 / 0 Регистрация: 11.11.2017 Сообщений: 4
	12.11.2017, 10:49 [ТС]	7
	Обалдеть, в две строки, хотела бы я так же программировать) Спасибо Вам! 0

Опции темы