How to find the minimum number of increments/decrements needed to make all array elements distinct ?

Правка en6, от yamih23436, 2021-03-31 06:50:30

Say , size of given array is $$$N$$$ and $$$abs(a[i])$$$<= 10000000

Example :

$$$ {1,100,100,100,100} $$$

Minimum cost = $$$4$$$

$$${1,100,101,99,102}$$$

I am looking for both $$$O(n*n)$$$ and $$$O(n)$$$ solutions .

Source of the problem : Just occurred to my mind .

My idea : Sort the given array , then apply the algorithm mentioned in this problem : https://mirror.codeforces.com/contest/713/problem/C

Теги #array

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский yamih23436 2021-03-31 06:50:30 77
en5 Английский yamih23436 2021-03-31 06:46:52 208
en4 Английский yamih23436 2021-03-31 06:44:29 4 Tiny change: 'st = $4$\n${1,100,' -> 'st = $4$\n\n\n${1,100,'
en3 Английский yamih23436 2021-03-31 06:33:34 4 Tiny change: 'um cost = 4\n\n${1,100,' -> 'um cost = $4\n$\n${1,100,'
en2 Английский yamih23436 2021-03-31 06:32:47 3
en1 Английский yamih23436 2021-03-31 06:32:10 360 Initial revision (published)