Минимизировать сумму баллов, присвоенных различным элементам, присутствующим в массиве

Для заданного массива arr[] размера N задача состоит в том, чтобы присвоить баллы каждому отдельному элементу массива так, чтобы сумма назначенных баллов была минимально возможной.

При начислении баллов необходимо выполнение следующих условий:

• Минимальное количество баллов, которое можно поставить за число, равно 1.
• Каждому отдельному элементу должно быть присвоено уникальное значение.
• Баллы должны быть присвоены в соответствии со значением числа, т.е. меньшим числам должны быть присвоены более низкие баллы по сравнению с большими числами.

Примеры:

Input: N = 5, arr[] = {10, 20, 10, 25}
Output: 7
Explanation: Assign 1 point to 10, 2 points to 20, 3 points to 25. Sum of points = 1 + 2 + 1 + 3 = 7, which is the minimum possible.

Input: N = 4, arr[] = {7, 7, 7, 7}
Output: 4
Explanation: Assign 1 point to 7. Sum of points = 1 + 1 + 1 + 1 = 4, which is the minimum possible.

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

• Инициализируйте переменную как 1 , чтобы сохранить требуемый результат.
• Отсортируйте заданный массив в порядке возрастания.
• Инициализируйте точку переменной как 1 , чтобы сохранить точки текущего элемента.
• Итерация в диапазоне [0, N-1], используя переменную i
  • Если arr[i] равно arr[i+1] , то увеличить ans на точку .
  • В противном случае увеличьте значение точки на 1 , а затем добавьте точку к ответу .
• Выведите значение ans в качестве результата.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*logN)
Вспомогательное пространство: O(1)