Question

Учёные рассматривают участок поверхности Марса, который можно представить в виде последовательности точек с высотами H1, H2, ..., HN. Высота между двумя соседними точками меняется равномерно. Для исследований необходимо собрать информацию с любого отрезка участка поверхности, длина которого равна K. Для этого запланировано выбрать некоторую точку L, высадить туда марсоход и отправить его последовательно по точкам HL, HL+1, ..., HL+K. Марсоход работает от аккумулятора. На перемещение на одну единицу вверх марсоход тратит одну единицу энергии. При перемещении на одну единицу вниз марсоход накапливает одну единицу энергии. На горизонтальное перемещение энергия не тратится. Изначально у марсохода достаточно энергии, чтобы изучить любой отрезок интересующего учёных участка, а максимальный возможный запас аккумулятора не ограничен. Учёные хотят, чтобы для дальнейших исследований у марсохода осталось как можно больше энергии. Поэтому среди всех возможных вариантов им нужно найти такое L, чтобы итоговый запас аккумулятора после исследований оказался максимально возможным. Если таких L несколько, для определённости берется минимальное из возможных. Помогите учёным найти номер стартовой точки L. Входные данные В первой строке входных данных содержится целое число N (2 ≤ N ≤ 250.000) — количество точек на интересующем учёных участке поверхности Марса. Во второй строке содержится целое число K (1 ≤ K < N) — длина отрезка, который должен пройти марсоход. В следующих N строках вводятся целые числа H1, H2, ..., HN (1 ≤ Hi ≤ 109) — высоты точек. Выходные данные Выведите единственное целое число L — номер стартовой точки для марсохода.

Answer 1

Ответ:

#include <iostream>

int main() {

  int arr[100], n, first = 0, second = 0;

  std::cin >> n;

  for (int i = 0; i < n; ++i)

      std::cin >> arr[i];

  for (int i = 1; i < n; ++i) {

      const int diff = arr[i] - arr[i - 1];

      if (diff > 0)

          if (arr[i] <= 2000)

              first += diff;

          else if (arr[i - 1] >= 2000)

              second += diff;

          else {

              first += 2000 - arr[i - 1];

              second += arr[i] - 2000;

           }

   }

  std::cout << first << ' ' << second;

  return 0;

Объяснение:

язык python

Answer 2

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

Понимание задачи:

1. Марсоход тратит энергию при движении вверх на единицу высоты и накапливает энергию при движении вниз на единицу высоты. На горизонтальное перемещение энергия не тратится. 2. Марсоход начинает с некоторой стартовой точки L и перемещается по выбранным точкам HL, HL+1, ..., HL+K.

Чтобы марсоход потратил как можно меньше энергии, он должен начать с точки, где высоты будут максимально учитывать последующее движение вниз или минимизировать движение вверх.

Давайте представим себе наилучший способ выбрать стартовую точку:

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

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

Как алгоритм:

1. Пройдите по первым K точкам и найдите максимальную высоту среди них. 2. Затем найдите индекс первой точки, в которой достигается эта максимальная высота. 3. Этот индекс будет номером стартовой точки L.

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