前缀和|二分查找|LeetCode2234| 花园的最大总美丽值

2023-12-13 06:11:52

作者推荐

贪心算法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]表示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;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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

文章来源:https://blog.csdn.net/he_zhidan/article/details/134845779
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。