Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2234.html
2234. Maximum Total Beauty of the Gardens
 Difficulty: Hard.
 Related Topics: Array, Two Pointers, Binary Search, Greedy, Sorting.
 Similar Questions: Split Array Largest Sum.
Problem
Alice is a caretaker of n
gardens and she wants to plant flowers to maximize the total beauty of all her gardens.
You are given a 0indexed integer array flowers
of size n
, where flowers[i]
is the number of flowers already planted in the ith
garden. Flowers that are already planted cannot be removed. You are then given another integer newFlowers
, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers target
, full
, and partial
.
A garden is considered complete if it has at least target
flowers. The total beauty of the gardens is then determined as the sum of the following:

The number of complete gardens multiplied by
full
. 
The minimum number of flowers in any of the incomplete gardens multiplied by
partial
. If there are no incomplete gardens, then this value will be0
.
Return the **maximum total beauty that Alice can obtain after planting at most newFlowers
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.
Constraints:

1 <= flowers.length <= 105

1 <= flowers[i], target <= 105

1 <= newFlowers <= 1010

1 <= full, partial <= 105
Solution

class Solution { public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) { int n = flowers.length; long[] prefix = new long[n + 1]; Arrays.sort(flowers); for (int i = 0; i < n; ++i) { prefix[i + 1] = prefix[i] + Math.min(flowers[i], target); } long res = 0; int i = n  1; for (int c = 0; c <= n; ++c) { long remain = prefix[n]  prefix[n  c] + newFlowers  c * (long) target; long min = 0; if (0 > remain) { break; } i = Math.min(i, n  c  1); while (0 <= i && (target <= flowers[i]  flowers[i] * (long) (i + 1)  prefix[i + 1] > remain)) { i; } if (0 <= i) { long dif = flowers[i] * (long) (i + 1)  prefix[i + 1]; min = Math.min(target  1L, flowers[i] + (remain  dif) / (i + 1)); if (i + 1 < n  c) { min = Math.min(min, flowers[i + 1]); } } res = Math.max(res, c * (long) full + min * partial); } return res; } }

# 2234. Maximum Total Beauty of the Gardens # https://leetcode.com/problems/maximumtotalbeautyofthegardens class Solution: def maximumBeauty(self, flowers: List[int], k: int, t: int, full: int, partial: int) > int: n = len(flowers) A = [min(t, x) for x in flowers] A.sort() if A[0] == t: return full * n if k >= t * n  sum(A): return max(full * n, full * (n  1) + partial * (t  1)) costs = [0] for i in range(1, n): costs.append(costs[1] + (i) * (A[i]  A[i  1])) j = n  1 while A[j] == t: j = 1 res = 0 while k >= 0: index = min(j, bisect_right(costs, k)  1) minIncomplete = A[index] + (k  costs[index]) // (index + 1) res = max(res, minIncomplete * partial + full * (n  j  1)) k = (t  A[j]) j = 1 return res
Explain:
nope.
Complexity:
 Time complexity : O(n).
 Space complexity : O(n).