I am unable to come up with a rough logic also. Help me 
I tried greedy approach. Didn’t seem to work.
I believe a greedy solution works :
Find frequency of every distinct element initially in the array, then for every distinct element, find the cost required to change the element to its just greater element (from original set of distinct elements, all of its occurrences ). Form a set of pair of (cost, value of element) and iterate on set till its size is more than k. In each iteration pick the best element in set or to say, the smallest pair and include its cost in the total cost and change the cost of element just greater than the current one in the set to point to the next greatest element of the current element.