Application of C++ prefix sum algorithm: minimal overhead of making arrays equal

Basic knowledge points involved in this article

C++ algorithm: principles, source code and test cases of prefix sum, prefix product, prefix XOR including course videos

Title

You are given two arrays nums and cost whose indexes start from 0, each containing n positive integers.
You can perform the following operations any number of times:
Increase or decrease any element in nums by 1.
The cost of performing an operation on the i-th element is cost[i].
Please return the minimum total cost to make all elements in nums equal.
Example 1:
Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: We can do the following to make all elements 2 :

  • Add the 0th element 1 time with a cost of 2.
  • Reduce the first element by 1 time with a cost of 3.
  • Reduce the 2nd element 3 times, the cost is 1 + 1 + 1 = 3.
    The total overhead is 2 + 3 + 3 = 8.
    This is minimal overhead.
    Example 2:
    Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
    Output: 0
    Explanation: All elements in the array are equal and no additional operations are required.
    Parameter range:
    n == nums.length == cost.length
    1 <= n <= 105
    1 <= nums[i], cost[i] <= 106
    The test case ensures that the output does not exceed 253-1.

Analysis

Principle

Assume that all numbers become x in the end, then the value range of x is [min(nums),max(nums)]. If x1 Assume x is x1 and the overhead is ll1. If x is x1 + 1, how will the overhead change.
If nums[i] is less than x Overhead increases, 1 more than before
If nums[i] equals x Overhead increases, remains unchanged before, now adds 1
If nums[i] is equal to x + 1 The overhead is reduced, before -1, now unchanged
If nums[i] is greater than x + 1 The overhead is reduced, 1 less than before

Time complexity

Divided into four steps, each time complexity is O(n), so the total time complexity is O(n).

Steps
一 Seeking general Add 1 to each value, reducing the consumption of 1. A value may have multiple or none
二 Add all numbers whose value is less than j 1 or reduce the consumption of 1, which is the prefix sum.
Three The consumption of all numbers becoming 0
Four enum x.

Code

Core code

class Solution {
public:
long long minCost(vector & amp; nums, vector & amp; cost) {
m_c = nums.size();
const int iMaxValue = *std::max_element(nums.begin(), nums.end());
vector vValueConst(iMaxValue + 1);//vValueConst[j] represents the cost of making all nums[i] equal to j plus or minus 1
for (int i = 0; i < m_c; i + + )
{
vValueConst[nums[i]] + = cost[i];
}
vector vSum = { 0 };//vValueConst[j] represents the cost of adding or subtracting 1 to all nums[i] for (const auto & amp; ll : vValueConst )
{
vSum.emplace_back(ll + vSum.back());
}
long long ll = 0; //Record the total cost of turning all values into x
for (int i = 0; i < m_c; i + + )
{
ll + = abs(nums[i] – 0LL) * cost[i];
}
long long llRet = LLONG_MAX;
for (int x = 0; x < iMaxValue; x + + )
{
//[0,x + 1) consumption increases
ll + = vSum[x + 1] – vSum[0];
//[x + 1,…)
ll -= vSum.back() – vSum[x + 1];
llRet = min(llRet, ll);
}
return llRet;
}
int m_c;
};

Test cases

int main()
{
Solution slug;
vector nums, cost;
long long res;
nums = { 1, 3, 5, 2 };
cost = { 2, 3, 1, 14 };
res = slu.minCost(nums,cost);
Assert(8LL ,res);

//CConsole::Out(res);

}

Old code in March 2023

class Solution {
public:
long long minCost(vector & amp; nums, vector & amp; cost) {
m_c = nums.size();
Init(nums,cost);
return Cost();
}
long long Cost()
{
long long llMin = (1000LL) * 1000 * 1000 * 1000 * 1000 * 1000;
long long llLeftCost = 0, llRightCost = 0;
for (int i = 1; i < m_c; i + + )
{
llRightCost + = abs((long long)m_vNums[i] – m_vNums[0])*m_vCost[i];
}
llMin = min(llMin, llLeftCost + llRightCost);

 for (int i = 1; i < m_c; i + + )
{
llLeftCost + = m_vSums[i]*(m_vNums[i] - m_vNums[i - 1]);
llRightCost -= (m_vSums.back() - m_vSums[i ])*(m_vNums[i] - m_vNums[i - 1]);
llMin = min(llMin, llLeftCost + llRightCost);
}
return llMin;
 }
 void Init(const vector<int> & amp; nums,const vector<int> & amp; cost)
 {
std::multimap<int, int> m;
for (int i = 0; i < m_c; i + + )
{
m.emplace(nums[i], cost[i]);
}
for (const auto & amp; it : m)
{
m_vNums.push_back(it.first);
m_vCost.push_back(it.second);
}
m_vSums.push_back(0);
for (const auto & amp; n : m_vCost)
{
m_vSums.push_back(m_vSums.back() + n);
}
 }
 int m_c;
 vector<int> m_vNums, m_vCost;
 vector<long long> m_vSums;

};

Extended reading

Video course

Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771

how fast do you want

A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176

Related downloads

If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653

| Full of positive energy, I have to tell everyone
|
|-|
|Rejoicing when you hear defects is a good wish, to find problems early, correct them early, and save money for the boss. |
| The origin of the Mohist name: Everything is recorded in Mohism. |
|If the program is a dragon, then the algorithm is his key point|

Test environment

Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:

VS2022 C++ 17