maximum-total-beauty-of-the-gardens

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Alice is a caretaker of <code>n</code> gardens and she wants to plant flowers to maximize the total beauty of all her gardens.

You are given a 0-indexed integer array <code>flowers</code> of size <code>n</code>, where <code>flowers[i]</code> is the number of flowers already planted in the <code>ith</code> garden. Flowers that are already planted cannot be removed. You are then given another integer <code>newFlowers</code>, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers <code>target</code>, <code>full</code>, and <code>partial</code>.

A garden is considered complete if it has at least <code>target</code> flowers. The total beauty of the gardens is then determined as the sum of the following:

<ul>
	<li>The number of complete gardens multiplied by <code>full</code>.</li>
	<li>The minimum number of flowers in any of the incomplete gardens multiplied by <code>partial</code>. If there are no incomplete gardens, then this value will be <code>0</code>.</li>
</ul>

Return the maximum total beauty that Alice can obtain after planting at most <code>newFlowers</code> flowers.

&nbsp;
Example 1:

<pre>
Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
Output: 14
Explanation: Alice can plant
- 2 flowers in the 0th garden
- 3 flowers in the 1st garden
- 1 flower in the 2nd garden
- 1 flower in the 3rd garden
The gardens will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers.
There is 1 garden that is complete.
The minimum number of flowers in the incomplete gardens is 2.
Thus, the total beauty is 1 * 12 + 2 * 1 = 12 + 2 = 14.
No other way of planting flowers can obtain a total beauty higher than 14.
</pre>

Example 2:

<pre>
Input: flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
Output: 30
Explanation: Alice can plant
- 3 flowers in the 0th garden
- 0 flowers in the 1st garden
- 0 flowers in the 2nd garden
- 2 flowers in the 3rd garden
The gardens will then be [5,4,5,5]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers.
There are 3 gardens that are complete.
The minimum number of flowers in the incomplete gardens is 4.
Thus, the total beauty is 3 * 2 + 4 * 6 = 6 + 24 = 30.
No other way of planting flowers can obtain a total beauty higher than 30.
Note that Alice could make all the gardens complete but in this case, she would obtain a lower total beauty.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= flowers.length &lt;= 105</code></li>
	<li><code>1 &lt;= flowers[i], target &lt;= 105</code></li>
	<li><code>1 &lt;= newFlowers &lt;= 1010</code></li>
	<li><code>1 &lt;= full, partial &lt;= 105</code></li>
</ul>

maximumBeauty

Maximum Total Beauty of the Gardens

Split Array Largest Sum

split-array-largest-sum

分割数组的最大值

Greedy

Array

Two Pointers

Binary Search

Enumeration

Prefix Sum

Sorting

Alice 是&nbsp;<code>n</code>&nbsp;个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

给你一个下标从 0&nbsp;开始大小为 <code>n</code>&nbsp;的整数数组&nbsp;<code>flowers</code>&nbsp;，其中&nbsp;<code>flowers[i]</code>&nbsp;是第 <code>i</code>&nbsp;个花园里已经种的花的数目。已经种了的花 不能&nbsp;移走。同时给你&nbsp;<code>newFlowers</code>&nbsp;，表示 Alice 额外可以种花的&nbsp;最大数目&nbsp;。同时给你的还有整数&nbsp;<code>target</code>&nbsp;，<code>full</code>&nbsp;和&nbsp;<code>partial</code>&nbsp;。

如果一个花园有 至少&nbsp;<code>target</code>&nbsp;朵花，那么这个花园称为 完善的&nbsp;，花园的 总美丽值&nbsp;为以下分数之 和 ：

<ul>
	<li>完善 花园数目乘以&nbsp;<code>full</code>.</li>
	<li>剩余 不完善&nbsp;花园里，花的 最少数目&nbsp;乘以&nbsp;<code>partial</code>&nbsp;。如果没有不完善花园，那么这一部分的值为&nbsp;<code>0</code>&nbsp;。</li>
</ul>

请你返回 Alice 种最多 <code>newFlowers</code>&nbsp;朵花以后，能得到的&nbsp;最大&nbsp;总美丽值。

&nbsp;

示例 1：

<pre>输入：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 。
</pre>

示例 2：

<pre>输入：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可以让所有花园都变成完善的，但这样她的总美丽值反而更小。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= flowers.length &lt;= 105</code></li>
	<li><code>1 &lt;= flowers[i], target &lt;= 105</code></li>
	<li><code>1 &lt;= newFlowers &lt;= 1010</code></li>
	<li><code>1 &lt;= full, partial &lt;= 105</code></li>
</ul>