•Статьи•12 месяцев назад

Техника двух указателей

Техника двух указателей часто используется в программировании для решения задач, связанных с массивами или последовательностями. Она заключается в использовании двух указателей, которые проходят по массиву с разных начальных позиций, двигаясь в одном или в противоположных направлениях с одной или с разной скоростью. Эта техника особенно полезна для решения задач, связанных с поиском, оптимизацией или обработкой массивов эффективным образом.

Приведем основные этапы работы техники двух указателей:

Инициализация: Устанавливаем начальное положение каждого из двух указателей или на одинаковых, или на разных позициях в массиве.
Перемещение: Попеременно перемещаем указатели на основе определенных условий, пока они не встретятся или не достигнут определенного условия. Перемещение указателей может контролироваться в соответствии с требованиями задачи. Например, один указатель может двигаться быстрее другого, или они могут двигаться в противоположных направлениях.
Проверка условий: На каждом шаге итерации совершается проверка выполнения определенных условий в соответствии с требованиями задачи. Эти условия часто определяют, нужно ли перемещать указатели, обновлять некоторые переменные или выполнять другие операции.
Завершение: Процесс продолжается до тех пор, пока один или оба указателя не достигнут конца массива, или пока они не встретятся, или пока не будет выполнено какое-то другое условие завершения.

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

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

Установим две переменнные $i$ и $j$ (назовем их указателями):

$i$ на начало массива $(i = 1)$ ;
$j$ на конец массива $(j = n)$ ;

Далее запустим while цикл, в котором:

значения $m [i]$ и $m [j]$ меняются местами;
после чего $i$ увеличивается на $1$ , а $j$ уменьшается на $1$ ;

Цикл продолжаем, пока указатели $i$ и $j$ не встретятся.

Отметим, что поменять значения $m [i]$ и $m [j]$ можно при помощи дополнительной переменной $t e m p$ , выполнив три операции:

Хусейн с Ярославом играют в карточки. На столе в ряд лежат $n$ карточек, на которых написаны различные числа. Игроки ходят по очереди. Первым ходит Хусейн. За один ход игрок может взять либо крайнюю слева карточку, либо крайнюю справа. Игрок всегда выбирает карточку с большим числом. Игра заканчивается, когда на столе не останется карточек. Найдите сумму чисел на карточках Хусейна и Ярослава к концу игры.

Вход. Первая строка содержит количество карточек $n (1 \leq n \leq 10000)$ на столе. Вторая строка содержит $n$ натуральных чисел, записанных на карточках. Все числа не превышают $1 0^{9}$ .

Выход. Выведите сумму чисел на карточках, которые собрали Хусейн и Ярослав к концу игры.

Открыть задачу

Пусть массив $m$ содержит числа, записанные на карточках. Инициализируем указатели $i = 0$ на начало массива и $j = n - 1$ на конец массива.

На каждом ходу игрок берет карточку с максимальным значением $ma x (m [i], m [j])$ , после чего карточка убирается со стола (совершаем операцию $i + +$ если выбрана карточка $m [i]$ и $j - -$ если выбрана карточка $m [j]$ ). Для каждого из игроков подсчитываем сумму выбранных карточек в двух переменных. Процесс продолжается до тех пор, пока все карточки не будут убраны со стола, то есть, пока указатели $i$ и $j$ не сойдутся.

Пример

Игра будет проходить следующим образом.

Объявим рабочие массивы. Сумму чисел на карточках Хусейна и Ярослава будем подсчитывать соответственно в $res [0]$ и $res [1]$ .

int m[10001], res[2];

Читаем входные данные.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Установим указатели $i = 0$ и $j = n - 1$ .

i = 0; j = n - 1;

Игроки последовательно совершают $n$ ходов. Ходы для четного $k$ совершает Хусейн, а ходы для нечетного $k$ совершает Ярослав. Соответственно, сумма Хусейна будет накапливаться в $res [0]$ , а сумма Ярослава — в $res [1]$ .

for (k = 0; k < n; k++)
{

На каждом ходу игрок выбирает карточку с максимальным значением $ma x (m [i], m [j])$ .

  if (m[i] > m[j])
    res[k % 2] += m[i++];
  else
    res[k % 2] += m[j--]; ;
}

Выводим ответ.

printf("%d %d\n", res[0], res[1]);

Хусейн разложил в ряд $n$ карточек с числами $a_{1}, a_{2}, a_{3}, ..., a_{n}$ . Затем он собрал их и разложил в другом порядке: $a_{1}, a_{3}, a_{5}, ..., a_{6}, a_{4}, a_{2}$ . Именно эту последовательность он и передал Ярославу. Помогите Ярославу восстановить исходную последовательность Хусейна.

Например, если Ярослав получил последовательность $(2, 4, 9, 4, 7, 6)$ , то Хусейну он должен вернуть последовательность $(2, 6, 4, 7, 9, 4)$ .

Вход. Первая строка содержит число $n (1 \leq n \leq 10000)$ — количество карточек. Вторая строка содержит $n$ натуральных чисел, записанных на карточках. Все числа не превышают $1 0^{9}$ .

Выход. Выведите исходную последовательность Хусейна.

Открыть задачу

У Хусейна есть строка, состоящая из символов $0$ и $1$ . Чтобы развлечься, он придумал следующую игру. Хусейн может выполнять одну из двух операций над строкой:

приписать с левого конца $0$ , а с правого $1$ ;
приписать с правого конца $0$ , а с левого $1$ ;

Например, из строки $010$ можно получить $00101$ или $10100$ .

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

Вход. Одна строка длины не более $1 0^{5}$ , содержащая только символы $0$ и $1$ .

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

Открыть задачу

Рассмотрим входную строку $s$ — результирующую строку Хусейна после выполнения всех операций. Инициализируем два указателя: $i = 0$ на начало и $j = n - 1$ на конец строки.

Если $s_{i} \neq = s_{j}$ , то на концах строки находятся разные символы. А именно или $0$ слева и $1$ справа, или $1$ слева и $0$ справа. Это значит, что предыдущая строка могла быть увеличена в результате применения одной из заданных операций. В этом случае сдвигаем оба указателя $i$ и $j$ на одну позицию навстречу друг другу и снова проверяем, могла ли подстрока $s [i ... j]$ быть получена в результате операций Хусейна.

Как только для текущей подстроки $s [i ... j]$ будет выполняться $s_{i} = s_{j}$ , ее уже нельзя получить при помощи данных операций. Выводим ее длину – это и будет исходная строка Хусейна.

Пример

Проведем операции Хусейна в обратном порядке.

Строка $s = "1"$ изначально была у Хусейна.

Читаем входную строку. Вычисляем ее длину в переменной $res$ .

cin >> s;
res = s.size();

Инициализируем два указателя: $i = 0$ на начало и $j = n - 1$ на конец строки.

i = 0; j = s.size() - 1;

Если $s_{i} \neq = s_{j}$ , то на концах строки находятся разные символы. Хусейн мог при помощи своей операции получить строку $s [i ... j]$ из строки $s [i + 1... j - 1]$ .

while ((i < j) && (s[i] != s[j]))
{

Сдвигаем оба указателя $i$ и $j$ на одну позицию навстречу друг другу и уменьшаем на $2$ текущий размер $res$ подстроки $s [i ... j]$ .

  i++; j--;
  res -= 2;
}

Выводим ответ.

cout << res << endl;

Задан массив $A$ , отсортированный по возрастанию и содержащий $n$ целых чисел. Определите, существует ли в нем такая пара чисел $(A_{i}, A_{j}), i < j$ , сумма которых равна $x$ .

Вход. Первая строка содержит два целых числа $n (n \leq 1 0^{5})$ и $x (x \leq 1 0^{6})$ . Вторая строка содержит $n$ целых неотрицательных чисел, каждое из которых не больше $1 0^{6}$ .

Выход. Выведите "YES" если такая пара элементов существует, и "NO" иначе.

Открыть задачу

Пусть $v$ — входной массив чисел. Инициализируем указатели $i = 0$ на начало массива, $j = n - 1$ на конец массива. Массив по условию задачи уже отсортирован.

Пока указатели $i$ и $j$ не встретятся, совершаем следующие действия:

Если $v_{i} + v_{j} = x$ , то искомая пара элементов найдена, выводим ее и завершаем программу.
Если $v_{i} + v_{j} < x$ , то двигаем указатель $i$ на одну позицию вправо. В этом случае сумма $v_{i} + v_{j}$ будет увеличиваться;
Если $v_{i} + v_{j} > x$ , то двигаем указатель $j$ на одну позицию влево. В этом случае сумма $v_{i} + v_{j}$ будет уменьшаться;

Пример

Рассмотрим первый тест. Инициализируем указатели. Промоделируем работу алгоритма. Значение $x = 13$ , ищем два числа с суммой $13$ .

Читаем входные данные.

scanf("%d %d", &n, &x);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Инициализируем указатели.

int i = 0, j = v.size() - 1;

Указатель $i$ двигаем вперед, указатель $j$ двигаем назад.

while (i < j)
{

Если $v_{i} + v_{j} = x$ , то искомая пара элементов найдена. Выводим ее и завершаем программу.

  if (v[i] + v[j] == x)
  {
    printf("YES\n");
    return 0;
  }

Если $v_{i} + v_{j} < x$ , то двигаем указатель $i$ на одну позицию вправо;

Если $v_{i} + v_{j} > x$ , то двигаем указатель $j$ на одну позицию влево;

  if (v[i] + v[j] < x) i++; else j--;
}

Если искомая пара не найдена, то выводим "NO".

printf("NO\n");

Задан массив целых чисел $A$ и целое число $x$ . Найдите такую тройку чисел $(A_{i}, A_{j}, A_{k})$ в массиве, сумма которых равна $x$ . Все индексы $i, j, k$ должны быть различны.

Вход. Первая строка содержит размер массива $n (n \leq 3 \cdot 1 0^{4})$ и значение $x (∣ x ∣ \leq 1 0^{9})$ . Вторая строка содержит $n$ целых чисел, каждое из которых по модулю не больше $1 0^{8}$ .

Выход. Если требуемая тройка чисел существует, то выведите ее в любом порядке. Если существует несколько троек, выведите любую. Если искомой тройки не существует, выведите $- 1$ .

Открыть задачу

Читаем входные данные.

cin >> n >> x;
v.resize(n);
for (i = 0; i < n; i++)
  cin >> v[i];

Сортируем входной массив.

sort(v.begin(), v.end());

Перебираем значения $k = 0, 1, ..., n - 3$ .

for (k = 0; k < n - 2; k++)
{

Ищем такую пару индексов $(i, j)$ , что $i > k$ и $v_{i} + v_{j} = x - v_{k} (i < j)$ . Инициализируем индексы $i$ и $j$ .

  i = k + 1; j = n - 1;
  s = x - v[k];

Используем технику двух указателей для поиска искомой пары $(i, j)$ .

  while (i < j)
  {
    if (v[i] + v[j] == s)
    {

Если пара $(i, j)$ найдена, то выводим искомую тройку чисел $(v_{k}, v_{i}, v_{j})$ .

      printf("%d %d %d\n", v[k], v[i], v[j]);
      return 0;
    }

Если $v [i] + v [j] < s$ , то двигаем указатель $i$ на одну позицию вправо;

Если $v [i] + v [j] > s$ , то двигаем указатель $j$ на одну позицию влево;

    if (v[i] + v[j] < s) i++; else j--;
  }
}

Если тройка чисел не найдена, то выводим $- 1$ .

cout << -1 << endl;

Задан отсортированный массив $A$ из $n$ целых чисел. Для каждого индекса $i$ найдите, сколько элементов в массиве лежит между $A_{i}$ и $2 \cdot A_{i}$ включительно.

Вход. Первая строка содержит размер $n (n \leq 1 0^{5})$ массива $A$ . Вторая строка содержит $n$ целых чисел в диапазоне от $0$ до $1 0^{9}$ в отсортированном порядке.

Выход. Выведите $n$ чисел. Для каждого индекса $i (1 \leq i \leq n)$ массива выведите количество элементов, лежащих между $A_{i}$ и $2 \cdot A_{i}$ включительно.

Открыть задачу

Интервал $A [i ... j]$ будем называть хорошим, если на нем находятся числа в промежутке $[A_{i}; 2 \cdot A_{i}]$ включительно (то есть $A_{j} \leq 2 \cdot A_{i}$ ).

Реализуем скользящее окно при помощи двух указателей $i$ и $j$ и будем его поддерживать так, чтобы текущий рассматриваемый интервал $[i ... j]$ был хорошим, а интервал $[i ... j + 1]$ плохим.

Например, для следующей последовательности

интервалы $[2; 2], [2; 3], [2; 4]$ и $[2; 5]$ являются хорошими.
интервалы $[2; 6], [2; 7]$ являются плохими.

Если $A_{j} \leq 2 \cdot A_{i}$ , то расширяем текущий интервал до $А [i ... j + 1]$ . Иначе сокращаем его до $А [i + 1... j]$ . Перед передвижением указателя $i$ выводим количество элементов, лежащих между $A_{i}$ и $2 \cdot A_{i}$ включительно. Оно равно $j - i$ .

Оценка сложности алгоритма линейная, то есть $O (n)$ .

Пример

Рассмотрим движение указателей для приведенного примера.

Для заданного состояния $A_{j} \leq 2 \cdot A_{i}$ , поэтому двигаем вперед указатель $j$ .

Теперь $A_{j} > 2 \cdot A_{i}$ . Вперед следует двигать указатель $i$ . Однако перед его перемещением выводим количество элементов, лежащих между $A_{i}$ и $2 \cdot A_{i}$ включительно. Оно равно $j - i = 6 - 2 = 4$ .

Двигаем $j$ вперед пока $A_{j} \leq 2 \cdot A_{i}$ .

Теперь $A_{j} > 2 \cdot A_{i}$ . Выводим ответ для $i = 3$ (он равен $j - i = 8 - 3 = 5$ ) и увеличиваем $i$ на $1$ .

Читаем входные данные.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Инициализируем указатели $i = j = 0$ .

i = j = 0;

Двигаем указатели вперед пока для каждого значения $i < n$ не будет найден ответ.

while (i < n) // [i..j]
{

Если $A_{j} \leq 2 \cdot A_{i}$ (но при этом $j$ не вышло за границы массива, то есть $j < n$ ), то расширяем текущий интервал, увеличивая указатель $j$ .

  if ((j < n) && (a[j] <= 2 * a[i])) j++;
  else
  {

При $A_{j} > 2 \cdot A_{i}$ выводим ответ для индекса $i$ и увеличиваем $i$ на единицу.

    printf("%d ", j - i);
    i++;
  }
}

Вдоль прекрасного Адриатического побережья расположено $n$ отелей. Каждый отель имеет свою стоимость в евро.

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

Вы должны рассчитать эту максимально возможную общую стоимость.

Вход. В первой строке заданы два целых числа $n$ и $m (1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m < 2^{31})$ . В следующей строке заданы $n$ натуральных чисел меньших $1 0^{6}$ , представляющих стоимости отелей в том порядке, в котором они расположены вдоль побережья.

Выход. Выведите искомую максимальную стоимость (оно будет больше $0$ во всех тестах).

Открыть задачу

Стоимости отелей занесем в массив $a$ . Интервал $[i ... j]$ будем называть хорошим, если сумма стоимостей отелей на нем не больше $m$ .

Реализуем скользящее окно при помощи двух индексов $i$ и $j$ и будем его поддерживать так, чтобы текущий рассматриваемый интервал $[i ... j]$ был хорошим. Пусть $s$ — сумма стоимостей отелей на интервале $[i ... j]$ . Если $s + a [j + 1] \leq m$ , то расширяем текущий интервал до $a [i ... j + 1]$ . Иначе сокращаем его до $a [i + 1... j]$ . Находим максимум среди стоимостей всех рассматриваемых хороших интервалов.

Пример

Рассмотрим движение указателей для приведенного примера.

$i = 0, j$ движется вперед пока сумма чисел на интервале $[i ... j]$ не больше $m = 12$ . Остановимся на интервале $[0...3]$ , так как на нем сумма равна $10$ , а на интервале $[0...4]$ сумма равна $15$ .
$i = 1, j$ подвинуть вперед не можем так как сумма на интервале $[1...4]$ равна $13$ .
$i = 2, j$ двигаем вперед до интервала $[2...4]$ .

Максимальное значение среди всех хороших интервалов равно $12$ и достигается на интервале $[2...4]$ .

Читаем входные данные.

scanf("%d %lld", &n, &m);

Инициализируем переменные:

в $res$ вычисляется максимальная стоимость среди стоимостей всех обрабатываемых хороших интервалов;
в $s$ поддерживается сумма чисел на текущем интервале $[i ... j]$ . Все числа текущего интервала $[i ... j]$ содержатся в очереди $q$ ;

s = res = 0;

Последовательно обрабатываем стоимости отелей.

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

Читаем и добавляем стоимость $v a l$ текущего отеля в очередь.

  scanf("%d", &val);
  q.push(val);

Обновляем сумму $s$ на интервале. Все элементы текущего интервала находятся в очереди $q$ .

  s += val;

Если сумма чисел на текущем интервале больше $s$ , то удаляем элементы с начала интервала.

  while (s > m)
  {
    s -= q.front();
    q.pop();
  }

Вычисляем максимальное значение $res$ среди сумм элементов допустимых интервалов (стоимость отелей на которых не превышает $m$ ).

  if (s > res) res = s;
}

Выводим ответ.

printf("%lld\n", res);

Реализуем скользящее окно с помощью двух указателей $i$ и $j$ . Для каждого фиксированного $i = 1, 2, ...$ будем по максимуму раздвигать интервал $[i ... j]$ так, чтобы сумма элементов на нем была не больше $x$ . То есть для каждого $i$ ищем такое наибольшее значение $j$ , что сумма элементов на интервале $[i ... j]$ не превышает $x$ , а сумма элементов на интервале $[i ... j + 1]$ уже больше $x$ .

Пусть $s$ — сумма чисел на интервале $[i ... j]$ . Если $s + a [j + 1] \leq m$ , то расширяем интервал до $[i ... j + 1]$ . Иначе сокращаем его до $[i + 1... j]$ . Подсчитываем количество интервалов с суммой $x$ .

Пример

Рассмотрим движение указателей для приведенного примера.

$i = 0$ , $j$ движется вперед, пока сумма чисел на интервале $[i ... j]$ не станет больше $x = 7$ . Остановимся на интервале $[0...2]$ , так как сумма чисел на нем равна $7$ , а на интервале $[0...3]$ сумма чисел уже равна $9$ .
$i = 1$ , $j$ двигаем вперед до $3$ . Сумма чисел на интервале $[1...3]$ равна $7$ , а на интервале $[1...4]$ уже $14$ .
$i = 2$ , рассматриваемый интервал $[2...3]$ . Сумма чисел на нем равна $3$ , однако двигать индекс $j$ вперед мы не можем, потому что сумма чисел на интервале $[2...4]$ равна $10$ , что больше $x = 7$ .
$i = 3$ , рассматриваемый интервал $[3...3]$ . Сумма чисел на нем равна $2$ , однако двигать индекс $j$ вперед мы не можем, потому что сумма чисел на интервале $[3...4]$ равна $9$ , что больше $x = 7$ .
$i = 4$ , рассматриваемый интервал $[4...4]$ . Сумма чисел на нем равна $7$ .

Количество подмассивов с суммой $x = 7$ равно $3$ . Они начинаются с индексов $0, 1$ и $4$ .

Объявим рабочий массив.

#define MAX 200001
long long a[MAX];

Читаем входные данные.

scanf("%d %lld", &n, &x);
for (i = 0; i < n; i++)
  scanf("%lld", &a[i]);

Изначально установим текущий интервал $[i ... j] = [0; 0]$ . Сумма чисел на этом интервале равна $s = 0$ .

s = j = 0;

Для каждого значения $i$ последовательно обрабатываем интервалы $[i ... j]$ .

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

Для фиксированного левого конца $i$ интервала $[i ... j]$ ищем наибольшее $j$ , для которого сумма элементов на указанном интервале не превосходит $x$ .

  while ((j < n) && (s + a[j] <= x)) s += a[j++];

Если сумма чисел $s$ на текущем интервале $[i ... j]$ равна $x$ , то искомое количество подмассивов $c n t$ увеличиваем на $1$ .

  if (s == x) cnt++;

Пересчитываем сумму чисел $s$ для интервала $[i + 1... j]$ .

  s -= a[i];
}

Выводим ответ.

printf("%lld\n", cnt);

Завтра Зия примет участие в соревновании последовательностей. Число $x \geq 0$ называется вершиной некоторой последовательности, если последовательность $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ является подпоследовательностью данной последовательности. Силой каждой последовательности считается ее наибольшая вершина.

Завтра все студенты пойдут на соревнование и победителем станет обладатель сильнейшей последовательности. Зия имеет последовательность $a_{1}, a_{2}, a_{3}, ..., a_{n}$ . Он хочет завладеть системой оценки соревнования и удалить из нее последовательности с большей силой, чем у него. Однако Зия не знает силу собственной последовательности, но очень хочет победить. Помогите ему определить силу собственной последовательности.

Вход. В первой строке задано количество $n (1 \leq n \leq 1 0^{5})$ чисел в последовательности Зии. В следующей строке записаны $n$ целых чисел $a_{i} (1 \leq a_{i} \leq 1 0^{5})$ — элементы последовательности.

Выход. Выведите одно число — силу данной последовательности.

Открыть задачу

Пусть $v$ — входной массив чисел. Инициализируем указатели $i = 0$ на начало массива и $j = n - 1$ на конец массива. В переменной $k$ будем подсчитывать силу последовательности. Изначально установим $k = 1$ .

Пока указатели $i$ и $j$ не встретятся, выполняем следующие действия:

Сдвигаем указатель $i$ на одну позицию вправо, если он не указывает на число $k$ ;
Сдвигаем указатель $j$ на одну позицию влево, если он не указывает на число $k$ ;
Если оба указателя указывают на число $k$ , увеличиваем $k$ на единицу и сдвигаем каждый из указателей на одну позицию в соответствующем направлении;

После завершения работы алгоритма ответом будет значение $k - 1$ .

Пример

Рассмотрим второй тест. Инициализируем указатели. Двигаем указатель $i$ вправо, а $j$ влево пока они не будут указывать на число $1$ .

Двигаем указатель $i$ вправо, а $j$ влево, пока они не будут указывать на число $2$ .

Указатели встретились, останавливаем алгоритм. Ответом будет значение $k = 2$ .

Читаем входные данные.

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Установим указатели на начало и конец массива $v$ .

int i = 0, j = v.size() - 1;

В переменной $k$ подсчитываем силу последовательности.

k = 1;
while (i <= j)
{

Указатель $i$ двигаем вправо пока не встретится число $k$ .

  if (v[i] != k) i++;

Указатель $j$ двигаем влево пока не встретится число $k$ .

  if (v[j] != k) j--;

Если оба указателя указывают на число $k$ , то увеличиваем $k$ на единицу.

  if (v[i] == k && v[j] == k) k++;
}

Выводим ответ.

printf("%d\n", k - 1);

Сегодня собрались $n$ программистов. У каждого программиста есть рейтинг, показывающий его силу. Рейтинг — это целое число от $0$ до $1 0^{9}$ . Ваш рейтинг как программиста равен $m$ . Со всех собравшихся сегодня программистов Вы хотите выбрать двух в свою команду. Их необходимо выбрать таким образом, чтобы сумма их рейтингов была максимальной, но не превышала Ваш рейтинг, поскольку Вы хотите быть лидером этой команды.

Вход. В первой строке заданы два целых числа: $n (2 \leq n \leq 1 0^{5})$ — количество программистов и $m (0 \leq m \leq 1 0^{9})$ — Ваш рейтинг. Во второй строке приведены $n$ целых чисел $r_{1}, r_{2}, ..., r_{n} (0 \leq r_{i} \leq 1 0^{9})$ — рейтинги программистов.

Выход. Выведите одно целое число — максимальную сумму рейтингов выбранных программистов или $- 1$ , если таких двух человек найти невозможно.

Открыть задачу

Отсортируем рейтинги программистов в массиве $v$ . Поиск двух программистов с максимальным суммарным рейтингом будем осуществлять при помощи техники двух указателей.

Инициализируем указатель $l o w = 0$ на начало массива и указатель $hi g h = n - 1$ на конец массива.

Среди всех возможных сумм $v [l o w] + v [hi g h]$ , не превышающих $m$ , находим максимальную. Если $v [l o w] + v [hi g h] \leq m$ , сдвигаем указатель $l o w$ вперед. В противном случае сдвигаем указатель $hi g h$ назад. Процесс передвижения указателей продолжаем до тех пор, пока они не встретятся.

Пример

Рассмотрим второй тест. Отсортируем числа и инициализируем указатели. Промоделируем работу алгоритма. В данном случае $m = 19$ : ищем два числа с максимальной суммой, не превышающей $19$ .

Читаем входные данные.

scanf("%d %d", &n, &m);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Сортируем рейтинги программистов.

sort(v.begin(), v.end());

Инициализируем указатели. В переменной $m x$ вычисляем максимальную сумму двух элементов.

int mx = -1, low = 0, high = n - 1;

Указатель $l o w$ двигаем вперед, указатель $hi g h$ двигаем назад.

while (low < high)
{

Среди всех возможных сумм $v [l o w] + v [hi g h]$ , не больших $m$ , находим максимум. Если $v [l o w] + v [hi g h] \leq m$ , то двигаем вперед $l o w$ . Иначе двигаем назад $hi g h$ .

  if (v[low] + v[high] <= m)
  {
    mx = max(mx, v[low] + v[high]);
    low++;
  }
  else high--;
}

Выводим ответ.

printf("%d\n", mx);

Корова Бесси, всегда увлекающаяся блестящими предметами, занялась добычей алмазов в свободное время! Она собрала $n$ алмазов разных размеров и хочет разместить некоторые из них в витрине в амбаре.

Поскольку Бесси хочет, чтобы алмазы в витрине были относительно похожи по размеру, она решила, что не будет включать в витрину два алмаза, если их размеры различаются более чем на $k$ (два алмаза могут быть выставлены вместе, если их размеры отличаются ровно на $k$ ). Зная значение $k$ , помогите Бесси определить максимальное количество алмазов, которые она сможет выставить в витрине.

Вход. Первая строка содержит $n (n \leq 1000)$ и $k (0 \leq k \leq 10000)$ . Каждая из следующих $n$ строк содержит одно целое число — размер одного алмаза. Все размеры — положительные числа, не превышающие $10000$ .

Выход. Выведите максимальное количество алмазов, которое Беси сможет продемонстрировать в витрине амбара.

Открыть задачу

Отсортируем массив с размерами алмазов. Для каждого индекса $i$ рассмотрим последовательность $m_{i}, m_{i + 1}, ..., m_{j}$ такую, что $∣ m_{j} - m_{i} ∣ \leq k$ , но при этом $∣ m_{j + 1} - m_{i} ∣ > k$ . Среди всех таких последовательностей найдем ту, которая содержит наибольшее количество элементов.

Пример

Отсортируем размеры алмазов.

Рассмотрим интервал $[0; 3]$ . Разница между размерами алмазов на нем не превышает $k = 3$ . Однако разместить в амбаре все алмазы в интервале $[0; 4]$ Бесси уже не сможет, так как $m_{4} - m_{0} > 3$ .

Объявим массив для хранения размеров алмазов.

int m[1000];

Читаем входные данные.

scanf("%d %d", &n, &k);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Отсортируем массив.

sort(m, m + n);

Максимальное количество алмазов, которое Беси сможет разместить в амбаре, подсчитываем в переменной $res$ .

res = 0;

Для каждого индекса $i$ рассматриваем последовательность $m_{i}, m_{i + 1}, ..., m_{j}$ наибольшей длины, такую, что $∣ m_{j} - m_{i} ∣ \leq k$ . Длину этой последовательности подсчитываем в переменной $c n t$ .

for (i = 0; i < n; i++)
{
  cnt = 0;
  for (j = i; j < n; j++)
  {

Как только условие $∣ m_{j} - m_{i} ∣ > k$ становится истинным, выходим из цикла.

    if (m[j] > m[i] + k) break;
    cnt++;
  }

Среди длин всех последовательностей находим наибольшую.

  if (cnt > res) res = cnt;
}

Выводим ответ.

printf("%d\n", res);

Имеется массив $h$ целых чисел длины $n$ , задающий высоты n вертикальных линий. Для каждой $i$ -й линии её конечные точки заданы координатами $(i, 0)$ и $(i, h_{i})$ .

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

Вход. Первая строка содержит размер $n (n \leq 1 0^{5})$ массива $h$ . Вторая строка содержит $n$ натуральных чисел — элементы массива $h$ , каждое из которых не превышает $1 0^{9}$ .

Выход. Выведите максимальный объём воды, который может удержать контейнер.

Открыть задачу

Сначала вычислим объем воды в контейнере между крайними верткальными линиями, то есть между линиями пары $(l, r) = (1, n)$ . Затем будем двигать указатели $l$ и $r$ навстречу друг другу:

если $h_{l} < h_{r}$ , то увеличим $l$ на $1$ ;
если $h_{l} \geq h_{r}$ , то уменьшим $r$ на $1$ ;

Объем воды между линиями $l$ и $r$ равен $min (h_{l}, h_{r}) * (r - l)$ . Среди всех полученных значений находим наибольшее.

Задачу можно решить за $O (n^{2})$ . Однако из-за ограничения $n \leq 1 0^{5}$ такое решение приведёт к превышению лимита времени (Time Limit). Достаточно перебрать пары линий $(i, j)$ , для которых $1 \leq i < j \leq n$ , и далее для каждой такой пары вычислить объем воды, который они могут удерживать. Среди всех вычисленных значений находим максимальный объём.

Пример

Контейнер из первого теста имеет вид:

Наибольшее количество воды можно удержать между линиями $2$ и $9$ . Высота уровня воды составит $7$ , а объем воды равен $7 \cdot 7 = 49$ .

Читаем входные данные.

scanf("%d", &n);
h.resize(n);
for (i = 0; i < n; i++)
  scanf("%lld", &h[i]);

В переменной $res$ будем хранить максимальное количество воды, которое может удерживать контейнер.

long long res = 0;

Инициализируем пару указателей $(l, r) = (1, n)$ .

int l = 0, r = h.size() - 1;

Двигаем указатели $l$ и $r$ навстречу друг другу, пока они не встретятся.

while (l < r)
{

Объем воды между линиями $l$ и $r$ равен $min (h_{l}, h_{r}) \cdot (r - l)$ . Среди всех таких объемов находим максимальный.

  res = max(res, min(h[l], h[r]) * (r - l));

Перемещаем указатели.

  if (h[l] < h[r])
    l += 1;
  else
    r -= 1;
}

Выводим ответ.

printf("%lld\n", res);

Вам дан список песен, которые играли на радио 106 FM. Всего в списке содержится $n$ песен. Найдите длину самого длинного фрагмента списка, состоящего из неповторяющихся песен.

Вход. Первая строка содержит количество песен $n (1 \leq n \leq 1 0^{5})$ в списке. Вторая строка содержит $n$ целых чисел $k_{1}, k_{2}, ..., k_{n} (1 \leq k_{i} \leq 1 0^{9} ‘)$ — идентификационные номера песен.

Выход. Выведите длину самого длинного фрагмента списка, состоящего из неповторяющихся песен.

Открыть задачу

Пусть массив $v$ хранит идентификационные номера песен. С помощью двух указателей будем поддерживать скользящее окно $[i; j]$ , в котором песни не повторяются. Иными словами, на отрезке $[i; j]$ все песни уникальны. Песни из этого отрезка будем хранить во множестве $s$ . Для каждого значения $i$ будем стремиться расширить отрезок до максимальной возможной длины. То есть для фиксированного $i$ будем искать такое $j$ , что на отрезке $[i; j]$ песни не повторяются, а на отрезке $[i; j + 1]$ уже появляются дубли.

При обработке текущей песни с индексом $j + 1$ имеются два варианта:

если песня $v_{j + 1}$ не встречается в отрезке $[i; j]$ , то добавляем ее в этот отрезок, расширяя его до $[i; j + 1]$ ;
если песня $v_{j + 1}$ уже присутствует в отрезке, сдвигаем левую границу $i$ вправо до тех пор, пока $v_{j + 1}$ не исчезнет из отрезка $[i; j]$ . Затем добавляем $v_{j + 1}$ в отрезок, расширяя его до $[i; j + 1]$ . При каждом сдвиге $i$ удаляем соответствующие элементы из множества $s$ ;

Среди всех возможных отрезков $[i; j]$ с уникальными песнями находим максимальную длину. Это и будет ответом на задачу.

Пример

Рассмотрим как будут изменяться отрезки с неповторяющимися песнями для первого примера.

Длина наибольшего отрезка равна $5$ .

Читаем входные данные. Идентификационные номера песен храним в массиве $v$ .

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Поддерживаем отрезок $[i; j - 1]$ из неповторяющихся песен (то есть песни от $v_{i}$ до $v_{j - 1}$ не повторяются). Во множестве $s$ храним идентификационные номера песен из этого отрезка. В переменной $res$ отслеживаем длину самого длинного фрагмента с уникальными песнями.

i = res = 0;
for (j = 0; j < n; j++)
{

Рассматриваем текущую песню с индексом $j$ . Если она уже содержится во множестве $s$ , то расширить текущий отрезок $[i; j - 1]$ за счет $j$ -ой песни не удастся. В этом случае необходимо сдвигать левую границу $i$ , удаляя из множества $s$ песню $v_{i}$ , до тех пор, пока $j$ -ая песня не исчезнет из множества $s$ .

  while (s.find(v[j]) != s.end())
  {
    s.erase(v[i]);
    i++;
  }

Добавим $j$ -ую песню в отрезок и, соответственно, во множество $s$ . Таким образом, отрезок $[i; j]$ не будет содержать повторяющихся песен.

  s.insert(v[j]);

Среди всех возможных отрезков $[i; j]$ находим самый длинный. Длина отрезка $[i; j]$ равна $j - i + 1$ .

  res = max(res, j - i + 1);
}

Выводим ответ.

printf("%d\n", res);

Список использованных задач

Комментарии (5)

azimzadenihad•12 месяцев назад

thanks for all

Eltaj13•12 месяцев назад

Thanks for the problems!

drizzy•1 год назад

Thanks for the problems! Will there be future topic contests like these ?

medv•1 год назад•2 ревизия

drizzy Thanks a lot if you liked it. By the way, problems "Competition of sequences", "The best team" and "Radio 106 FM" are taken from the past official Azerbaijan School Competitions

drizzy•1 год назад

medv Please continue this series of topic wise contests. Thanks

Загрузка

Момент, получаем данные с сервера