Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 21

Description

Minimum Cost to Make Array Equal

You are given two 0-indexed arrays nums and cost consisting each of n positive integers.

You can do the following operation any number of times:

• Increase or decrease any element of the array nums by 1.

The cost of doing one operation on the ith element is cost[i].

Return the minimum total cost such that all the elements of the array nums become equal.

Example 1:

Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: We can make all the elements equal to 2 in the following way:
- Increase the 0th element one time. The cost is 2.
- Decrease the 1st element one time. The cost is 3.
- Decrease the 2nd element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.

Example 2:

Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Explanation: All the elements are already equal, so no operations are needed.

Constraints:

• n == nums.length == cost.length
• 1 <= n <= 105
• 1 <= nums[i], cost[i] <= 106

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  long long minCost(vector<int>& nums, vector<int>& cost) {
    int len = nums.size();
    vector<pair<int, int>> pairs;
    pairs.reserve(len);
    for(int i = 0; i < len; ++i) {
      pairs.push_back({nums[i], cost[i]});
    }
    sort(pairs.begin(), pairs.end());

    long long costs = 0;
    long long addOneCost = pairs[0].second;
    long long minusOneCost = 0;
    for(int i = len - 1; i > 0; --i) {
      costs += 1LL * (pairs[i].first - pairs[0].first) * (pairs[i].second);
      minusOneCost += pairs[i].second;
    }
    long long answer = costs;
    for(int i = 1; i < len; addOneCost += pairs[i].second, minusOneCost -= pairs[i].second, ++i) {
      if(pairs[i].first == pairs[i - 1].first) {
        continue;
      }
      int diff = pairs[i].first - pairs[i - 1].first;
      costs += 1LL * diff * addOneCost;
      costs -= 1LL * diff * minusOneCost;
      answer = min(costs, answer);
    }

    return answer;
  }
};

// Accepted
// 48/48 cases passed (92 ms)
// Your runtime beats 89.42 % of cpp submissions
// Your memory usage beats 47.08 % of cpp submissions (40.8 MB)