Minions and War

We need to make all element equal in this problem and also find minimum cost. This problem can be solved in many was. Let describe author's solution.

Firstly, count the frequency of every element of the array. Let’s calculate the total sum of the array. Initialize two variable with 0. Let call them cur and tot.

Then, let's iterate every possible element i, from 1 to 1000000, for every i:

• Add frequency[i] × i to cur, and frequency[i] to tot.
• Now, the calculation part for i, we need to increase (tot × i) - cur for making tot elements equal to i, so we need **P × ((tot × i) - cur) ** here.
  On the other hand, we need to decrease (sum - cur) - ((n - tot) × i) for making n-tot elements equal to i, so we need Q × ((sum - cur) - ((n - tot) × i)) cost here. So we need total P × ((tot × i) - cur) + Q × ((sum - cur) - ((n - tot) × i)) cost to make every element equal to i.

The minimum cost among every possible i is the answer.