Make writing a habit together! This is the 15th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

describe

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 0-indexed 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 be 0.

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 will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers 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.Copy the code

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]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers 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.Copy the code

Note:

1 <= flowers.length <= 10^5
1 <= flowers[i], target <= 10^5
1 <= newFlowers <= 10^10
1 <= full, partial <= 10^5
Copy the code

parsing

Alice is the keeper of n gardens, and she wants to plant flowers to maximize the overall beauty of all her gardens.

Given a zero-indexed integer array flowers of size n, flowers[I] is the number of flowers already planted in the ith garden. Flowers that have been planted cannot be picked. You are then given another integer newFlowers, which is the maximum number of additional flowers That Alice can plant. The parameters target, full, and partial are also given.

A garden is considered complete if it has at least target flowers. Then the overall aesthetic value of all gardens was determined as the sum of the following items:

  • Multiply the number of full gardens by full
  • Partial times the minimum number of flowers in an incomplete garden. Partial is 0 if there are no incomplete gardens

Returns the maximum overall aesthetic feeling that Alice can obtain after planting newFlowers at most.

In order to maximize the overall beauty of all gardens, the algorithm is partial + complete * full. So will all the garden after sorting, the overall train of thought is in the position of the traverse all, find a suitable location, make its are incomplete in front of the garden, and make its most flowers most largest, for behind it are complete garden, make all the biggest garden overall beauty, more details and specific comments ideas I put in the code, This version of the code is probably the easiest to understand, and I have found several solutions on the forums, but they are all too obscure to follow.

The time complexity is O(NlogN), and the space complexity is O(N).

His solution is easy to understand, I also combined with the diagram is easier to understand: leetcode.com/problems/ma…

answer

class Solution(object): def maximumBeauty(self, flowers, newFlowers, target, full, partial): Flowers = [min(target, a) for a in flowers] * partial + partial * full flowers.sort() # if the smallest flowers in the partial are greater than or equal to target, If min(flowers) == target: Len (flowers) return full * len(flowers) # if newFlowers is greater than or equal to the number of flowers that target needs to fill all flowers with If newFlowers >= target * len(flowers) -sum (flowers): Return Max (full * len(flowers), full * (len(flowers) -1) + partial * (target-1)) Cost = [0] for I in range(1, len(flowers)) cost = [0] for I in range(1, len(flowers)) Pre = cost[-1] cost. Append (pre + I * (flowers[I] -flowers [i-1])) J = len(flowers) -1 while flowers[j] = target: j -= 1 ans = 0 Idx = min(j, bisect_right(cost, newFlowers) -1) # fill all incomplete gardens with the same number of flowers as those indexed by IDX. And evenly populate the remaining flowers into gardens indexed idX and before, Bar = flowers[idx] + (newflowers-cost [idx]) // (idx + 1) Bar * partial + full * (len(flowers) -j-1)) bar * partial + full * (len(flowers) -j-1)) Update newFlowers and j newFlowers -= (target-flowers [j]) j -= 1 return ansCopy the code

The results

Runtime: 1085 MS, faster than 100.00% of Python online submissions for Maximum Total Beauty of the Gardens. Memory Usage: Submissions in Python online submissions for Maximum Total Beauty of the Gardens.Copy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation