Мусорщик

Данная задача представляет собой частный случай задачи «Космические исследования», которая предлагалась школьникам на региональном этапе Всероссийской олимпиады школьников по информатике в 2010/2011 учебном году. Для решения задачи «Мусорщик» можно использовать частичное решение задачи «Космические исследования» при k=1. Заметим, что это значительно упрощает решение и дает возможность использования относительно несложного динамического алгоритма для полного решения задачи.

Поскольку вниз движение невозможно и «Мусорщику» нужно посетить все загрязненные сектора, то находясь в какой-то строке, прежде чем двигаться выше, необходимо посетить самые крайние сектора из всех имеющихся в данной строке. Также понятно, что посещение крайних загрязненных секторов строки гарантирует посещение всех секторов между ними, включая все загрязненные, поэтому все загрязненные сектора, имеющие в своей строке соседей слева и справа, могут быть исключены из рассмотрения. Таким образом, нам предстоит обойти не более 100 секторов (по 2 в каждой строке при n=50) . Координаты этих ключевых секторов удобно хранить в массивах l[y] и r[y], в которых будут содержаться соответственно левая крайняя и правая крайняя границы в строке y. Если в y-ой строке всего один загрязненный сектор, то l[y]=r[y]=x, где (x,y) – координата этого сектора. В случае отсутствия загрязненных секторов в y-ой строке положим, что l[y]=r[y]=0. Заполнить массивы l[y] и r[y] можно совместно с чтением данных координат секторов:

  read(n)
  top=l=r=0
  while(n--){
    read(x,y)
    top=max(y,top) 
    r[y]=max(x,r[y])
    if(x < l[y] or l[y]=0) l[y]=x
  }

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

На основании вышесказанного, несложно теперь составить динамическую модель решения данной. Пусть dl[y] – наименьшее количество шагов, которые нужно выполнить для того, чтобы оказаться на крайнем левом элементе в y-ой строке и посетить все загрязненные сектора данной строки. dr[y] – аналогичное значение для правого крайнего элемента. Для y=1 решение очевидно: dl[1]=dr[1]=r[1]-1, если r[1]>0 и dl[1]=dr[1]=0 иначе. Зная dl[y-1] и dr[y-1] можно вычислить dl[y] и dr[y], рассмотрев 4 возможных варианта движения. В тех случаях, когда объектов в строке y нет, можно полагать, что dl[y]=dl[y-1]+1 и dr[y]=dr[y-1]+1, также для определенности и будущих вычислений следует определять l[y]=l[y-1] и r[y]=r[y-1]. Как только y достигнет значения top – самой верхней строки с загрязненными секторами (максимального y, при котором r[y]>0) мы сразу же получим ответ в виде min(dl[top], dr[top]). Заметим, что сложность рассмотренного нами алгоритма линейна.

Алгоритмическая реализация основной части:

  l[0]=r[0]=1; dl[0]=dr[0]=-1
  for y=1..top
    if(l[y]){
      dl[y] = min(dl[y-1]+|r[y]-l[y-1]|, dr[y-1]+|r[y]-r[y-1]|)+r[y]-l[y]+1
      dr[y] = min(dl[y-1]+|l[y]-l[y-1]|, dr[y-1]+|l[y]-r[y-1]|)+r[y]-l[y]+1
    } else {
      l[y]=l[y-1]; r[y]=r[y-1]
      dl[y]=dl[y-1]+1; dr[y]=dr[y-1]+1
    }
  write(min(dl[top],dr[top]))

[Обсуждение] [Все попытки] [Задача]