网站关键字优化软件,学多久可以做网站 知乎,南通做网站ntwsd,wordpress企业模板免费作者推荐
【动态规划】【广度优先】LeetCode2258:逃离火灾
本文涉及的基础知识点
二分查找算法合集 滑动窗口
题目
给你一个下标从 0 开始长度为 n 的整数数组 stations #xff0c;其中 stations[i] 表示第 i 座城市的供电站数目。 每个供电站可以在一定 范围 内给所有城…作者推荐
【动态规划】【广度优先】LeetCode2258:逃离火灾
本文涉及的基础知识点
二分查找算法合集 滑动窗口
题目
给你一个下标从 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
分析
时间复杂度(logmn)其中m是可能的最大的最小电量std::accumulate(stations.begin(), stations.end(),0LL) k
二分查找
判断所有城市的电量能否达到midmid为0的时候一定可以随着mid增加变得不可能。求最后一个可能的mid显然左闭右开的二分。
Can函数
llSum记录当前城市的最大电量k还可以建造的电站数量stations记录各城市的电站数包括新建的
如果当前城市电量不够则建设电站到本城市电量更好满足要求。如果无法建造则失败。选择能给本城市供电的城市中最右的城市建造电站。
代码
核心代码
class Solution {
public:long long maxPower(vectorint stations, int r, int k) {m_c stations.size();long left 0, right std::accumulate(stations.begin(), stations.end(),0LL) k 1;while (right - left 1){const auto mid left (right - left) / 2;if (Can(stations, mid, r, k)){left mid;}else{right mid;}}return left;}bool Can(vectorint stations, const long long llMin, const int r,int k){long long llSum 0;for (int i 0; i r; i){//stations[r]下面循环加llSum stations[i];}for (int i 0; i stations.size(); i){const int iDel i - r - 1;if (iDel 0){llSum - stations[iDel];}const int iAdd i r;if (iAdd m_c){llSum stations[iAdd];}if (llSum llMin){const long long llNeed llMin - llSum;if (k llNeed){return false;}k- llNeed;llSum llMin;stations[min(iAdd, m_c - 1)] llNeed;}}return true;}int m_c;
};测试用例
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorint stations;int r, k;{Solution slu;stations { 1, 2, 4, 5, 0 };r 1, k 2;auto res slu.maxPower(stations, r, k);Assert(5LL, res);}{Solution slu;stations { 4,4,4,4 };r 0, k 3;auto res slu.maxPower(stations, r, k);Assert(4LL, res);}//CConsole::Out(res);
} 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 如无特殊说明本算法用**C**实现。
