10568. Коллекционер алмазов (бронза)

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

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

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

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

Пример входа	Пример выхода
5 3 1 6 4 3 1	4

РЕШЕНИЕ

два указателя

Анализ алгоритма

Отсортируем массив с размерами алмазов. Для каждого индекса i рассмотрим последовательность m_i, m_i+1, …, m_j такую, что | m_j – m_i | ≤ k, но при этом | m_j+1 – m_i | > k. Среди всех таких последовательностей найдем ту, которая содержит наибольшее количество элементов.

Пример

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

Рассмотрим интервал [0; 3]. Разница между размерами алмазов на нем не превышает k = 3. Однако разместить в амбаре все алмазы в интервале [0; 4] Бесси уже не сможет, так как m₄ – m₀ > 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 | ≤ k. Длину этой последовательности подсчитываем в переменной cnt.

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);