Подразделы

Другие разделы

Дата и время

21/11/2024 17:12:48

Авторизация

Зарегистрироваться
Восстановить пароль

Занятие 7

Общие приёмы повышения эффективности программы Сортировка Сканирование, метод двух указателей Структуры данных

Сканирование, метод двух указателей

Поиск подпоследовательности с максимальной суммой можно выполнить за время `O(N^3)`, перебирая все комбинации начала и конца этой последовательности и вычисляя сумму. Если предварительно вычислить частичные суммы, то время уменьшится до `O(N^2)`. Но существует простой алгоритм, работающий за `O(N)` и основанный на следующей идее. Если подпоследовательность имеет неотрицательную сумму элементов, то её выгодно включить в максимальную подпоследовательность. Т.е. можно рассматривать подпоследовательность в качестве составной части искомой подпоследовательности, пока сумма её элементов неотрицательна.

int maxseq(int a[], int n, int &i1, int &i2)
{ int i, i0=0, s=0, ms=0;
  i1=0;
  i2=-1;
  for(i=0; i<n; ++i)
  {
    s+=a[i];
    if(s<0)
    { i0=i+1; // начало последовательности
      s=0;
    }
    else if(ms<s) // лучше ранее найденной
    { i1=i0;
      i2=i;
      ms=s;
    }
  }
  return ms;
}

Длина прямой, покрытой отрезками, вычисляется с помощью сканирования – движения вдоль прямой, по точкам изменения состояния. В данном случае такими точками являются левые и правые концы отрезков. Эти точки нужно отсортировать по координатам. Если часть прямой между предыдущей и очередной точкой покрыта хотя бы одним отрезком, то его длину нужно добавить к суммарной длине покрытия.

int n; // количество отрезков
pair<int,int> o[30000];
cin>>n;
for(int i=0;i<n;++i)
{ int l,r;
  cin>>l>>r; 
  o[i*2].first=l;
  o[i*2].second=1; // начало отрезка
  o[i*2+1].first=r;
  o[i*2+1].second=-1; // конец отрезка
}
sort(o,o+2*n);
int x=-100000000, // предыдущая особая точка
  k=0, // текущее количество активных отрезков
  p=0; // суммарная длина покрытия
for(int i=0;i<2*n;++i)
{
  int d=o[i].first-x; // расстояние от предыдущей до текущей особой точки
  if(k>0) p+=d;
  k+=o[i].second;
  x=o[i].first; 
}
cout<<p<<"\n";

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

Найти подстроку минимальной длины, содержащую ровно `n` символов 'A'.