3月旧代码
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; };
8月旧代码
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; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 充满正能量得对大家说 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 算法终将统治宇宙，而我们统治算法。《喜缺全书》 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开
发环境： VS2022 C++17
