Блог пользователя Impostor_Syndrome

Minimum size of array possible?
Автор Impostor_Syndrome, история, 2 года назад, По-английски

In an array — 'arr' there are n elements. Two elements arr[i] and arr[j] can be combined to one element if arr[i] >= k * arr[j], for i != j. After combination, these two elements cannot further combine with any other element of the array. Find the minimum size of the array possible, after executing atmost n/2 operations.

Input will be n, the array elements and k.

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Please share source/link to the problem statement.

→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

When the order of the elements does not matter (as in the problem you described), it is generally a good idea to sort the array and assume the elements in order when coming up with a solution.
This said, each match decreases the size of the array by one, therefore the final size will be $$$n - matches$$$. If the final size has to be minimal, you want to maximize the numbers of matches.

One possible way of doing it:
→ Ответить