C++前缀和算法的应用：最大化城市的最小供电站数目（二）

class Solution {
public:
long long maxPower(vector& 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;
};

class Solution {
public:
long long maxPower(vector& 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;
};