#2234

Maximum Total Beauty of the Gardens

international master · 1970 · lc hard +32 · verified · 30.4% accepted · 451 likes · top 8%

⚑ Converging Pointers (Pair / Triple Sum)

Description

Alice tends n gardens and wants to maximize their combined beauty through additional planting.

You are given a 0-indexed integer array flowers of size n where flowers[i] is the existing flower count in garden i (already-planted flowers cannot be removed). You are also given newFlowers (the maximum additional flowers Alice may plant), along with integers target, full, and partial.

A garden is complete when it has at least target flowers. Total beauty is:

 - The number of complete gardens times full, plus

 - The minimum flower count across all incomplete gardens times partial (this term is 0 when no incomplete gardens remain).

Return the maximum total beauty achievable by planting at most newFlowers additional flowers.

Example 1:

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.

Example 2:

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.

Code

1
2
3