You are given two 0-indexed arrays nums and cost consisting each of npositive 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
Test cases are generated in a way that the output doesn't exceed 253-1
Solutions
Solution 1: Prefix Sum + Sorting + Enumeration
Let's denote the elements of the array nums as $a_1, a_2, \cdots, a_n$ and the elements of the array cost as $b_1, b_2, \cdots, b_n$. We can assume that $a_1 \leq a_2 \leq \cdots \leq a_n$, i.e., the array nums is sorted in ascending order.
Suppose we change all elements in the array nums to $x$, then the total cost we need is:
where $k$ is the number of elements in $a_1, a_2, \cdots, a_n$ that are less than or equal to $x$.
We can use the prefix sum method to calculate $\sum_{i=1}^{k} b_i$ and $\sum_{i=1}^{k} a_ib_i$, as well as $\sum_{i=k+1}^{n}a_ib_i$ and $\sum_{i=k+1}^{n}b_i$.
Then we enumerate $x$, calculate the above four prefix sums, get the total cost mentioned above, and take the minimum value.
The time complexity is $O(n\times \log n)$, where $n$ is the length of the array nums. The main time complexity comes from sorting.
implSolution{#[allow(dead_code)]pubfnmin_cost(nums:Vec<i32>,cost:Vec<i32>)->i64{letmutzip_vec:Vec<_>=nums.into_iter().zip(cost.into_iter()).collect();// Sort the zip vector based on numszip_vec.sort_by(|lhs,rhs|lhs.0.cmp(&rhs.0));let(nums,cost):(Vec<i32>,Vec<i32>)=zip_vec.into_iter().unzip();letmutsum:i64=0;for&cin&cost{sum+=casi64;}letmiddle_cost=(sum+1)/2;letmutcur_sum:i64=0;letmuti=0;letn=nums.len();whilei<n{if(cost[i]asi64)+cur_sum>=middle_cost{break;}cur_sum+=cost[i]asi64;i+=1;}Self::compute_manhattan_dis(&nums,&cost,nums[i])}#[allow(dead_code)]fncompute_manhattan_dis(v:&Vec<i32>,c:&Vec<i32>,e:i32)->i64{letmutret=0;letn=v.len();foriin0..n{ifv[i]==e{continue;}ret+=((v[i]-e).abs()asi64)*(c[i]asi64);}ret}}
Solution 2: Sorting + Median
We can also consider $b_i$ as the occurrence times of $a_i$, then the index of the median is $\frac{\sum_{i=1}^{n} b_i}{2}$. Changing all numbers to the median is definitely optimal.
The time complexity is $O(n\times \log n)$, where $n$ is the length of the array nums. The main time complexity comes from sorting.