Application of C++ prefix sum algorithm: Maximizing the minimum number of power supply stations in the city

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
dichotomy

Title

Give you an integer array stations with subscripts starting from 0 and length n, where stations[i] represents the number of power supply stations in the i-th city.
Each power supply station can provide power to all cities within a certain range. In other words, if the given range is r, the power supply station at city i can supply power to all cities j that satisfy |i – j| <= r and 0 <= i, j <= n - 1.
|x| represents the absolute value of x. For example, |7 – 5| = 2, |3 – 10| = 7.
The power of a city is the number of power stations that can supply it.
The government has approved the construction of k additional power stations. You need to decide where these power stations should be built. These power stations have the same power supply range as the existing power stations.
Given two integers r and k, if additional power stations are built with the optimal strategy, return the maximum number of minimum power stations in all cities.
These k power supply stations can be built in multiple cities.
Example 1:
Input: stations = [1,2,4,5,0], r = 1, k = 2
Output: 5
explain:
One of the best solutions is to build both power supply stations in city 1.
The number of power supply stations in each city is [1,4,4,5,0] respectively.

The number of power supply stations in city 0 is 1 + 4 = 5.
The number of power supply stations in city 1 is 1 + 4 + 4 = 9.
The number of power supply stations in city 2 is 4 + 4 + 5 = 13.
The number of power supply stations in city 3 is 5 + 4 = 9.
The number of power supply stations in city 4 is 5 + 0 = 5.
The minimum number of power stations is 5.
No better solution can be found, so we return 5 .
Example 2:
Input: stations = [4,4,4,4], r = 0, k = 3
Output: 4
explain:
No matter how arranged, there is always a city with a number of power supply stations of 4, so the optimal solution is 4.
Parameter range:
n == stations.length
1 <= n <= 105
0 <= stations[i] <= 105
0 <= r <= n - 1
0 <= k <= 109

Analysis

Time complexity

O(nlogm), m= sum(stations) + k.

First level loop

If the minimum number of power supply stations in any city is greater than or equal to llTarget, then the minimum number of power supply stations in any city must be llTarget-1. If there are multiple ones that meet the conditions, we return the last one. Obviously use the two points of left closing and right opening. How many power supply stations can there be under extreme circumstances? All power stations (built and buildable) can supply all cities.

Second level loop

When the current urban power supply stations are insufficient, sufficient power supply stations will be built in the right city.

Variable description


i	Current city
llTarget	Let all cities have at least iTarget power supply stations
llNeed	How many new power supply stations are needed to have at least iTarget power supply stations in all cities?
stations	Power supply stations in each city (new, existing )
llHas	Power supply stations that can supply power to the current city, including power supply stations established to deal with previous cities
left	The leftmost city that supplies power to the current city
right	can power the current city The rightmost city

Attention

r can be larger than stations.size()

Code

Core code

class Solution {<!-- -->
public:
long long maxPower(vector<int> & amp; stations, int r, int k) {<!-- -->
m_iR = r;
m_iK = k;
m_stations = stations;
long long left = 0, right = std::accumulate(stations.begin(), stations.end(),0LL) + k + 1;
//Close left and open right
while (right - left > 1)
{<!-- -->
const long long mid = left + (right - left) / 2;
if (TargetNeed(mid))
{<!-- -->
left = mid;
}
else
{<!-- -->
right = mid;
}
}
return left;
}
//How many power supply stations need to be built if all city power supply stations reach iTarget?
bool TargetNeed(long long llTarget)
{<!-- -->
vector<int> stations = m_stations;
long long llHas = 0;
int left = 0;
int right = min(m_iR, (int)stations.size() - 1);//[left,right] represents the power stations that can supply power to this city
for (int i = 0; i <= right; i + + )
{<!-- -->
llHas + = stations[i];
}
long long llNeed = 0;
auto Add = [ & amp;]()
{<!-- -->
const long long curNeed = llTarget - llHas;
if (curNeed > 0)
{<!-- -->
llNeed + = curNeed;
if (llNeed > m_iK)
{<!-- -->
return false;
}
stations[right] + = curNeed;
llHas + = curNeed;
}
return true;
};
if (!Add())
{<!-- -->
return false;
}
for (int i = 1; i < stations.size(); i + + )
{<!-- -->
if (i - left > m_iR)
{<!-- -->
llHas -= stations[left];
left + + ;
}
if (right + 1 < stations.size())
{<!-- -->
right + + ;
llHas + = stations[right];
}
if (!Add())
{<!-- -->
return false;
}
}
return true;
}
int m_iR;
int m_iK;
vector<int> m_stations;
};

Test cases

template
void Assert(const vector & amp; v1, const vector & amp; v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i + + )
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T & t1, const T & t2)
{
assert(t1 == t2);
}

int main()
{
Solution slug;
vector stations = { 1, 2, 4, 5, 0 };
int r = 0;
int k = 0;
long long res;
stations = { 1, 2, 4, 5, 0 };
r = 1, k = 2;
res = slu.maxPower(stations, r, k);
Assert(5LL, res);
stations = {1};
r = 0, k = 3;
res = slu.maxPower(stations, r, k);
Assert(4LL, res);
stations = { 0 };
r = 0, k = 0;
res = slu.maxPower(stations, r, k);
Assert(0LL, res);
stations = { 4, 4, 4, 4 };
r = 0, k = 3;
res = slu.maxPower(stations, r, k);
Assert(4LL, res);
stations.assign(2, 1);
r = 1;
k = 1;
res = slu.maxPower(stations, r, k);
Assert(3LL, res);
stations.assign(100000, 100000);
r = 100000;
k = 1e9;
res = slu.maxPower(stations, r, k);
Assert(long long(1e10 + 1e9 + 0.5), res);
//CConsole::Out(res);
}

Old code from March

class Solution {
public:
long long maxPower(vector & amp; stations, int r, int k) {
m_c = stations.size();
CalPower(stations, r);
long long left = *std::min_element(m_vPower.begin(),m_vPower.end());
long long right = left + k + 1;
while (left + 1 < right)
{
long long iMid = (left + right) / 2;
if (Can(iMid,r,k))
{
left = iMid;
}
else
{
right = iMid;
}
}
return left;
}
void CalPower(vector stations,int r)
{
long long llCur = 0;
for (int i = 0; i < r; i + + )
{
llCur + = stations[i];
}
for (int i = 0; i < stations.size(); i + + )
{
if (i + r < m_c)
{
llCur + = stations[i + r];
}
if (i – r – 1 >= 0)
{
llCur -= stations[i – r – 1];
}
m_vPower.push_back(llCur);
}
}
bool Can(long long llMinPower, int r, int k)const
{
long long llAdd = 0;
vector vDiff(m_vPower.size());
for (int i = 0; i < m_vPower.size(); i + + )
{
llAdd + = vDiff[i];
const long long llNeedAdd = llMinPower – (m_vPower[i] + llAdd);
if (llNeedAdd <= 0 )
{
continue;
}
if (llNeedAdd > k )
{
return false;
}
const int iNewIndex = i + r + r + 1;
if (iNewIndex < m_c)
{
vDiff[iNewIndex] -= llNeedAdd;
}
llAdd + = llNeedAdd;
k -= llNeedAdd;
}
return true;
}
vector m_vPower;
int m_c;
};

August old code

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

I am full of positive energy and say it to everyone
It is a good wish to be happy when you hear the flaws. Discover problems early, correct them early, and save your boss money.
The origin of the Mohist name: everything is recorded in Mohism.
Algorithms will eventually rule the universe, and we will rule the algorithms. “The Complete Book of Xi Que”

Test environment

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

Development environment: VS2022 C++ 17