Can we solve by processing elements in sorted order and selecting element with the highest cost as the one we don't increment (and increment all other duplicates by one) every time we encounter duplicate elements?

You can do it greedily in one sweep. Iterate over the values (1 to 1000000000), whenever there are multiple entries that have that value push all except the most expensive into a heap and whenever there is a value that doesn't have any index place the most expensive that's currently in the heap on that value and update total cost accordingly. It's in $$$O(n \log{n})$$$ if you don't iterate over all values but jump to the next existing value whenever your heap is empty.

What's wrong with sorting and then noticing that only the most expensive smallest element will remain; the rest will be incremented. Then, the only the 2nd most expensive element from all elements <= 2nd smallest will remain, and so on.

For example, if our original array consisted of [1,1,1,2,2,3] then iterate from 1, let the most expensive element remain and all the rest of 1's costs get added and they get moved to 2. Then for 2, only the 2nd highest cost will remain at 2 from all the elements <= 2. Do the same thing and move the rest up to 3. Then for 3, only the third highest cost remains at 3 and so on.

This can be done with a SortedList or heap or whatever. Then, to get the answer, you take the sum of costs in the SortedList and subtract the kth highest cost at element k and accumulate this in an answer variable. This will loop over every element as it must get placed somewhere in O(n log n)?

will it work just sort according to costs and picking up element and inserting in set if already present then find out the next to it which is not present in set then add that cost in O(nlogn)

hey I have a solution

Explanation

Priority queue (pq) is made such that

• The element with the smallest value comes first.

• If two elements have the same value, the one with the larger cost comes first.

This helps ensure that the most costly operations are performed first when resolving duplicates.

Algorithm

1. The priority queue processes each element in ascending order of their values.
2. If the current element is distinct, i.e. it doesn't equal the prev value (which tracks the last processed distinct number), the element is kept as it is and no cost is involved.
3. If the current element is a duplicate (i.e., num == prev), we increments the element by 1 (i.e., changes the value of the current element) and add the associated cost in our ans (i.e. totalCost).
4. The modified element (i.e. num + 1) is pushed back into the priority queue to be re-evaluated, as it might still be a duplicate of another number.

C++ Code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct cmp {
    bool operator()(pair<ll,ll>& a, pair<ll,ll>& b) {
        if(a.first != b.first) {
            return a.first > b.first;
        }
        return a.second < b.second;    
    }
};

 int solve(vector<ll>& arr, vector<ll>& cost) {
    int totalCost = 0;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, cmp> pq;

    for(int i=0; i<int(arr.size()); i++) {
        pq.push({arr[i], cost[i]});
    }
    
    int prev = -1;
    while(!pq.empty()) {
        auto num = pq.top().first;
        auto cost = pq.top().second;

        if(num != prev) {
            //cout << num << " ";
            prev = num;
        }
        else {
            totalCost += cost;
            pq.push({num+1, cost});
        }
     pq.pop();
    }
  return totalCost;
 }

int main()
{
 vector<long long> arr = {1,2,2,3,3,4}, cost = {7,5,10,8,1,5};
 int ans = solve(arr,cost);
 cout << "\n ans = " << ans;
 return 0;
}

The heap/greedy solution is easy to follow. But what if we allow both increment and decrement to the elements in the array? The greedy idea doesn't seem to work anymore, right?