网站架构师招聘,wordpress登录非常慢,千博医院网站模板,文化建设的本质是什么作者推荐
贪心算法LeetCode2071:你可以安排的最多任务数目
本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
二分查找算法合集
题目
Alice 是 n 个花园的园丁#xff0c;她想通过种花#xff0c;最大化她所有花…作者推荐
贪心算法LeetCode2071:你可以安排的最多任务数目
本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
二分查找算法合集
题目
Alice 是 n 个花园的园丁她想通过种花最大化她所有花园的总美丽值。 给你一个下标从 0 开始大小为 n 的整数数组 flowers 其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花 不能 移走。同时给你 newFlowers 表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target full 和 partial 。 如果一个花园有 至少 target 朵花那么这个花园称为 完善的 花园的 总美丽值 为以下分数之 和 完善 花园数目乘以 full. 剩余 不完善 花园里花的 最少数目 乘以 partial 。如果没有不完善花园那么这一部分的值为 0 。 请你返回 Alice 种最多 newFlowers 朵花以后能得到的 最大 总美丽值。 示例 1 输入flowers [1,3,1,1], newFlowers 7, target 6, full 12, partial 1 输出14 解释Alice 可以按以下方案种花
在第 0 个花园种 2 朵花在第 1 个花园种 3 朵花在第 2 个花园种 1 朵花在第 3 个花园种 1 朵花 花园里花的数目为 [3,6,2,2] 。总共种了 2 3 1 1 7 朵花。 只有 1 个花园是完善的。 不完善花园里花的最少数目是 2 。 所以总美丽值为 1 * 12 2 * 1 12 2 14 。 没有其他方案可以让花园总美丽值超过 14 。 示例 2 输入flowers [2,4,5,3], newFlowers 10, target 5, full 2, partial 6 输出30 解释Alice 可以按以下方案种花在第 0 个花园种 3 朵花在第 1 个花园种 0 朵花在第 2 个花园种 0 朵花在第 3 个花园种 2 朵花 花园里花的数目为 [5,4,5,5] 。总共种了 3 0 0 2 5 朵花。 有 3 个花园是完善的。 不完善花园里花的最少数目为 4 。 所以总美丽值为 3 * 2 4 * 6 6 24 30 。 没有其他方案可以让花园总美丽值超过 30 。 注意Alice可以让所有花园都变成完善的但这样她的总美丽值反而更小。 提示 1 flowers.length 105 1 flowers[i], target 105 1 newFlowers 1010 1 full, partial 105
分析
时间复杂度
O(targetlogn)n是花园数量。枚举不完善花园的花的最少数目时间复杂度O(target)二分查找能让多少花园完善时间复杂度O(n)。
分情况讨论
如果能让所有花园完善没有非完善花园有非完善花园枚举非完善花园最少的花数目
注意
iMin 有效的条件 一至少一个花园的数目小于等于iMIn。 二将花园数目少于iMin的全部补到iMin。 在确保有1个非完善花园的情况下尽可能多的补完善花园。
完善花园的数目
由于前i个花园已经补了花所以vNeed只对这i个花园以外的花园有效。 由于前面i个花园已经补充到iMin个所以前i个花园只需要target-iMin个。 必须保留至少一个非完善花园
变量解析
vNeedvNeed[i]表示i1个完美花园需要多少树由于升序排序所以从后
面向前补 |
llSum|记录 flowers[0,i)之和
iFullNum|完善花园数
# 代码
## 核心代码
class Solution {
public:long long maximumBeauty(vectorint flowers, long long newFlowers, int target, int full, int partial) {m_c flowers.size();sort(flowers.begin(), flowers.end());vectorlong long vNeed;//vNeed[i]表示i1个完美花园需要多少树for (int i m_c - 1; i 0; i--){const int iCurNeed max(0, target - flowers[i]);vNeed.emplace_back((vNeed.size()?vNeed.back():0) iCurNeed);}long long llRet (vNeed.back() newFlowers)?(long long)full*m_c:0;long long llSum 0;for (int iMin 0,i 0 ; iMin target; iMin){while ((i m_c) (flowers[i] iMin)){llSum flowers[i];//llSum记录 flowers[0,i)之0i是长度}if (0 i){continue;}const long long llMinNeed (long long)iMin * i - llSum;if (llMinNeed newFlowers){break;//无法确保最小值为iMin。}long long iFullNum std::upper_bound(vNeed.begin(), vNeed.end(), newFlowers - llMinNeed)- vNeed.begin();//确保所有花园大于等于iMin的情况下能有多少完美花园iFullNum min(iFullNum, (long long)m_c - i);iFullNum (newFlowers - llMinNeed - ((0 iFullNum) ? 0: vNeed[iFullNum - 1]))/(target-iMin);//余下的花能将flowers[0,i)中的多少花园弄成完美花园iFullNum min(iFullNum, (long long)m_c - 1);llRet max(llRet, (long long)partial * iMin (long long)full * iFullNum);}return llRet;}int m_c;
};测试用例
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() { vector flowers; long long newFlowers; int target, full, partial; long long res; { Solution slu; flowers { 1, 3, 1, 1 }, newFlowers 7, target 6, full 12, partial 1; auto res slu.maximumBeauty(flowers, newFlowers, target, full, partial); Assert(14LL, res); } { Solution slu; flowers { 2, 4, 5, 3 }, newFlowers 10, target 5, full 2, partial 6; auto res slu.maximumBeauty(flowers, newFlowers, target, full, partial); Assert(30LL, res); } { Solution slu; flowers { 18,16,10,10,5 }, newFlowers 10, target 3, full 15, partial 4; auto res slu.maximumBeauty(flowers, newFlowers, target, full, partial); Assert(75LL, res); } { Solution slu; flowers { 36131,31254,5607,11553,82824,59230,40967,69571,36874,38700,81107,28500,61796,54371,23405,51780,75265,37257,86314,32258,47254,76690,18014,21538,96700,15094,57253,57073,7284,24501,21412,69582,15724,43829,81444,78281,88953,6671,94646,31037,89465,86033,27431,30774,48592,26067 }, newFlowers 2304903454, target 48476, full 5937, partial 15214; auto res slu.maximumBeauty(flowers, newFlowers, target, full, partial); Assert(737765815LL, res); } { Solution slu; flowers { 3,3 }; newFlowers 100000, target 3, full 3, partial 3; auto res slu.maximumBeauty(flowers, newFlowers, target, full, partial); Assert(6LL, res); }
//CConsole::Out(res);}
2023 年旧版
class Solution { public: long long maximumBeauty(vector flowers, long long newFlowers, int target, int full, int partial) { m_c flowers.size(); std::sort(flowers.begin(), flowers.end()); vector vFullNeed; for (int i m_c - 1; i 0; i–) { const int iNeed target - flowers[i]; if (iNeed 0 ) { const long long iPre vFullNeed.size() ? vFullNeed.back() : 0; vFullNeed.emplace_back(iNeed iPre); } else { vFullNeed.emplace_back(0); } } vector vSum(1); for (const auto i : flowers) { vSum.push_back(vSum.back() i); } long long llRet 0; for (int iMin flowers.front(); iMin target; iMin) { int iLessEqualNum std::upper_bound(flowers.begin(), flowers.end(), iMin) - flowers.begin(); long long llNeed (long long)iMin * iLessEqualNum - vSum[iLessEqualNum]; if (llNeed newFlowers) { break; } if (target iMin) { llRet max(llRet, (long long)full* m_c); break; } int iFullNum std::upper_bound(vFullNeed.begin(), vFullNeed.end(),newFlowers - llNeed ) - vFullNeed.begin(); iFullNum min(iFullNum, m_c - iLessEqualNum); long long llUpFlowers newFlowers - llNeed - ((0 iFullNum) ? 0 : vFullNeed[iFullNum - 1]); const int iUpNum min((long long)iLessEqualNum - 1, llUpFlowers / (target - iMin)); iFullNum iUpNum; llRet max(llRet, (long long)fulliFullNum (long long)partial * iMin); } if (flowers.front() target) { return (long long)full m_c; } return llRet; } 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
