Question

Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться. Входные данные В первой строке через пробел заданы два целых числа M и N (1 ≤ N < M ≤ 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 ≤ L, H ≤ 101). Ступеньки нумеруются снизу вверх. Выходные данные В выходной файл выведите единственное число - ответ на задачу. Примеры входные данные 5 3 4 2 1 2 5 2 1 2 2 1 выходные данные 3

Answer 1

Ответ:

Задачка мне очень понравилась, прилагаю решение на C#, консольное приложение

Объяснение:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Археологи_строители

{ class Program

   {

       static void Main(string[] args)

       {

           //Объявляем и задаем переменные "M" и "N", а так же переменную для результата

           int M,N=new int();

           int MyResult = 0;

           Console.WriteLine("Ведите Текущее количество ступенек и Сколько их должно быть:");

           M = int.Parse(Console.ReadLine());

           N = int.Parse(Console.ReadLine());

           // Создаем массив для хранения данных о ступенях. M-Количество ступенек, Цифра - для колонок длины и высоты

           int[,] mass = new int[M,2];

           // Запись значений в массив

           for (int x = 0; x < M; x++){

               for (int y = 0; y < 2; y++){

                   if (y==0){  //Чисто для юзерфрендли отображения

                       Console.Write($"Введите значение Длины для ступеньки №{x + 1}= ");} else{

                       Console.Write($"Введите значение Высоты для ступеньки №{x + 1}= ");}

                   mass[x, y] = Convert.ToInt32(Console.ReadLine());}

                   Console.WriteLine();}

           /* Как оказалось, самый простой способ определить какую же ступеньку надо "поднимать"-

            * это вычислить площадь гипотетически "заполняемого" пространства над ступенькой и взять

            * наименьшее значение.

            *  

            * Итак, допустим если у нас 5 ступенек, то нам нам необходимо записать 4 значения

            * (в рамках лестницы) площади заполняемых ступенек.

            *  

            * Перемножаем Длину ступеньки N на высоту ступеньки N+1, M-1 раз и сохраняем в массив

            */

           int M2 = M; //Дублируем изначальное число ступенек для контроля цикла

           for (int z = 0; z <M2-N; z++)

           {

               int[] acreage = new int[M - 1];

               for (int x = 0; x < M - 1; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       acreage[x] = mass[x, 0] * mass[x + 1, 1];

                   }

               }

               /*

                * И так у нас есть все значения гипотетически заполняемой ступеньки.

                * Ищем минимальное значение площади  

                */

               int minAcreage = acreage[0];

               for (int i = 0; i < M - 1; i++)

               {

                   if (minAcreage > acreage[i])

                   {

                       minAcreage = acreage[i];

                   }

               }

               MyResult = MyResult+minAcreage; //Плюсуем данное значение в переменную результата

               // У нас есть минимальная площадь. Найдем номер данной ступеньки

               int IndexAcreage = Array.IndexOf(acreage, minAcreage);

               //"Достроим нужную нам ступеньку и запишем обновленные данные во временный массив"

               int[,] tempMass = new int[M - 1, 2]; //Он на размер меньше, т.к. и "полных" ступенек у нас стало меньше

               for (int x = 0; x < M - 1; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       //Ступеньки до IndexAcreage мы просто переписываем во временный массив

                       if (x < IndexAcreage)

                       {

                           tempMass[x, y] = mass[x, y];

                       }

                       //2 ступеньки от IndexAcreage мы превращаем в одну (застраивая их блоками)

                       else if (x == IndexAcreage)

                       {

                           tempMass[x, y] = mass[x, y] + mass[x + 1, y];

                       }

                       /* и после IndexAcreage мы та же копируем, но со сдвигом вправо, т.к. полноценных  

                        * ступенек стало меньше

                        */

                       else if (x > IndexAcreage)

                       {

                           tempMass[x, y] = mass[x + 1, y];

                       }

                   }

               }

               M = M - 1; //Поскольку ступенек теперь меньше, то и их фактическое число необходимо уменьшить

               for (int x = 0; x < M + 1; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       mass[x, y] = 0;

                   }

               }

               //переписываем данные в основной массив и запускаем следющую интерацию цикла

               for (int x = 0; x < M; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       mass[x, y] = tempMass[x, y];

                   }

               }

           }

           Console.WriteLine($"Минимально необходимое число блоков: {MyResult}");

           Console.ReadKey(true);

       }

   }

}

Answer 2

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

Для этого можно использовать жадный алгоритм. Сначала отсортируем заданные ступеньки по их высоте (по убыванию) и будем последовательно добавлять их к новой лестнице, пока не достигнем N ступенек.

Исходя из примера входных данных:

makefileCopy code
M = 5 (общее количество ступенек)
N = 3 (количество ступенек новой лестницы)
Ступеньки: (длина, высота)
4 2
1 2
5 2
1 2
2 1

Сортируем ступеньки по убыванию высоты:

Copy code
5 2
4 2
1 2
1 2
2 1

Теперь будем добавлять ступеньки к новой лестнице, пока не достигнем N ступенек:

Copy code
1-я ступенька: 5 2 (5x2x1 = 10 блоков)
2-я ступенька: 4 2 (4x2x1 = 8 блоков)
3-я ступенька: 1 2 (1x2x1 = 2 блока)

Теперь у нас есть лестница с N = 3 ступеньками и общим количеством блоков равным 10 + 8 + 2 = 20 блоков.

Ответ на задачу: 20 блоков.

Если N ступенек уже достигнуто, можно просто остановить алгоритм и вывести результат.

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