Diamond Collector (Bronze)#10568

Diamond Collector (Bronze) (Editorial)

Sort the array of diamond sizes. For each index $i$ , consider the sequence $m_{i}, m_{i + 1}, ..., m_{j}$ m_i, m_{i+1}, ..., m_j such that $∣ m_{j} - m_{i} ∣ \leq k$ | m_j - m_i | \le k, but at the same time, $∣ m_{j + 1} - m_{i} ∣ > k$ | m_{j+1} - m_i | > k. Among all such sequences, find the one that contains the largest number of elements.

Example

Sort the sizes of the diamonds.

Consider the interval $[0; 3]$ . The difference between the sizes of the diamonds in this interval does not exceed $k = 3$ k = 3. However, Bessie will not be able to showcase all the diamonds in the interval $[0; 4]$ in the barn, since $m_{4} - m_{0} > 3$ m_4 - m_0 > 3.

Algorithm realization

Declare an array to store the sizes of the diamonds.

int m[1000];

Read the input data.

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

Sort the array.

sort(m, m + n);

The maximum number of diamonds that Bessie can display in the barn is counted in the variable $r es$ .

res = 0;

For each index $i$ , consider the sequence $m_{i}, m_{i + 1}, ..., m_{j}$ m_i, m_{i+1}, ..., m_j of the greatest length such that $∣ m_{j} - m_{i} ∣ \leq k$ | m_j - m_i | \le k. Count the length of this sequence in the variable $c n t$ .

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

As soon as the condition $∣ m_{j} - m_{i} ∣ > k$ | m_j - m_i | > k becomes true, exit the loop.

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

Among the lengths of all sequences, find the maximum.

  if (cnt > res) res = cnt;
}

Print the answer.

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