作者推荐
本文涉及的基础知识点
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个。
必须保留至少一个非完善花园
变量解析
| vNeed | vNeed[i]表示i+1个完美花园需要多少树，由于升序排序，所以从后 |
面向前补 | llSum|记录 flowers[0,i)之和 iFullNum|完善花园数 # 代码 ## 核心代码 class Solution { public: long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) { m_c = flowers.size(); sort(flowers.begin(), flowers.end()); vector<long long> vNeed;//vNeed[i]表示i+1个完美花园需要多少树 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)之0，i是长度 } 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; };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
