大型网站制作都有哪些,工作总结ppt模板免费,网站建设以后就业方向,杭州钱塘区本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 二分法
题目
给你一个下标从 0 开始长度为 n 的整数数组 stations #xff0c;其中 stations[i] 表示第 i 座城市的供电站数目。 每个供电站可以在一定 范围 内给所…本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 二分法
题目
给你一个下标从 0 开始长度为 n 的整数数组 stations 其中 stations[i] 表示第 i 座城市的供电站数目。 每个供电站可以在一定 范围 内给所有城市提供电力。换句话说如果给定的范围是 r 在城市 i 处的供电站可以给所有满足 |i - j| r 且 0 i, j n - 1 的城市 j 供电。 |x| 表示 x 的 绝对值 。比方说|7 - 5| 2 |3 - 10| 7 。 一座城市的 电量 是所有能给它供电的供电站数目。 政府批准了可以额外建造 k 座供电站你需要决定这些供电站分别应该建在哪里这些供电站与已经存在的供电站有相同的供电范围。 给你两个整数 r 和 k 如果以最优策略建造额外的发电站返回所有城市中最小供电站数目的最大值是多少。 这 k 座供电站可以建在多个城市。 示例 1 输入stations [1,2,4,5,0], r 1, k 2 输出5 解释 最优方案之一是把 2 座供电站都建在城市 1 。 每座城市的供电站数目分别为 [1,4,4,5,0] 。
城市 0 的供电站数目为 1 4 5 。城市 1 的供电站数目为 1 4 4 9 。城市 2 的供电站数目为 4 4 5 13 。城市 3 的供电站数目为 5 4 9 。城市 4 的供电站数目为 5 0 5 。 供电站数目最少是 5 。 无法得到更优解所以我们返回 5 。 示例 2 输入stations [4,4,4,4], r 0, k 3 输出4 解释 无论如何安排总有一座城市的供电站数目是 4 所以最优解是 4 。 参数范围 n stations.length 1 n 105 0 stations[i] 105 0 r n - 1 0 k 109
分析
时间复杂度
O(nlogm)m sum(stations)k。
第一层循环
如果任何城市的最小供电站数大于等于llTarget则任何城市的最小供电站数一定llTarget-1如果有多个满足条件的我们返回最后一个。显然用左闭右开的二分。极限情况下能有多少供电站所有供电站已建和可建的)都可以供应所有城市。
第二层循环
当前城市供电站不足的时候在right城市建立足够的供电站。
变量说明
i当前城市llTarget让所有城市至少有iTarget个供电站llNeed让所有城市至少有iTarget个供电站需要新建多少个供电站stations各城市供电站新建、已有之和llHas能给当前城市供电的供电站包括处理之前城市而建立的供电站left给当前城市供电的最左城市right能给当前城市供电的最右城市
注意
r可以大于stations.size()
代码
核心代码
class Solution {
public:long long maxPower(vectorint 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;//左闭右开while (right - left 1){const long long mid left (right - left) / 2;if (TargetNeed(mid)){left mid;}else{right mid;}}return left;}//所有城市供电站达到iTarget需要新建多少供电站bool TargetNeed(long long llTarget){vectorint stations m_stations;long long llHas 0;int left 0;int right min(m_iR, (int)stations.size() - 1);//[left,right]表示能够给此城市供电的电站for (int i 0; i right; i){llHas stations[i];}long long llNeed 0; auto Add [](){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 (right1 stations.size()){right;llHas stations[right];}if (!Add()){return false;}}return true;}int m_iR;int m_iK;vectorint m_stations;
};测试用例
template void Assert(const vector v1, const vector 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 slu; 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(1e101e90.5), res); //CConsole::Out(res); }
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 k1 ; 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 k1 ; 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 C17 或者 操作系统win10 开
发环境 VS2022 C17
