2234. Maximum Total Beauty of the Gardens

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution { public: long long maximumBeauty(vector& flowers, long long newFlowers, int target, int full, int partial) { const long long n = flowers.size(); // If a garden is already complete, clamp it to target. for (int& flower : flowers) flower = min(flower, target); sort(begin(flowers), end(flowers)); // All gardens are complete, so nothing we can do. if (flowers[0] == target) return n * full; // Have many new flowers can maximize the beauty value. if (newFlowers >= n * target - accumulate(begin(flowers), end(flowers), 0LL)) return max(n * full, (n - 1) * full + static_cast(target - 1) * partial); long long ans = 0; long long leftFlowers = newFlowers; // cost[i] := cost to make flowers[0..i] the same vector cost(n); for (long long i = 1; i < n; ++i) // Plant (flowers[i] - flowers[i - 1]) flowers for flowers[0..i - 1]. cost[i] = cost[i - 1] + i * (flowers[i] - flowers[i - 1]); int i = n - 1; // flowers' index (flowers[i + 1:] are complete) while (flowers[i] == target) --i; for (; leftFlowers >= 0; --i) { // To maximize the min # of incomplete flowers, we find the first index j // that we can't make flowers[0..j] equal to flowers[j], then we know we // can make flowers[0..j - 1] equal to flowers[j - 1]. In the meantime, // evenly increase each of them to seek a bigger min value. const int j = firstGreater(cost, i, leftFlowers); const long long minIncomplete = flowers[j - 1] + (leftFlowers - cost[j - 1]) / j; ans = max(ans, (n - 1 - i) * full + minIncomplete * partial); leftFlowers -= max(0, target - flowers[i]); } return ans; } private: int firstGreater(const vector& A, int maxIndex, long long target) { return upper_bound(begin(A), begin(A) + maxIndex + 1, target) - begin(A); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) { final long n = flowers.length; // If a garden is already complete, clamp it to target. for (int i = 0; i < n; ++i) flowers[i] = Math.min(flowers[i], target); Arrays.sort(flowers); // All gardens are complete, so nothing we can do. if (flowers[0] == target) return (long) n * full; // Have many new flowers can maximize beauty value. if (newFlowers >= n * target - Arrays.stream(flowers).asLongStream().sum()) return Math.max(n * full, (n - 1) * full + (long) (target - 1) * partial); long ans = 0; long leftFlowers = newFlowers; // cost[i] := cost to make flowers[0..i] the same long[] cost = new long[flowers.length]; for (int i = 1; i < flowers.length; ++i) // Plant (flowers[i] - flowers[i - 1]) flowers for flowers[0..i - 1]. cost[i] = cost[i - 1] + i * (flowers[i] - flowers[i - 1]); int i = flowers.length - 1; // flowers' index (flowers[i + 1:] are complete) while (flowers[i] == target) --i; for (; leftFlowers >= 0; --i) { // To maximize the min # of incomplete flowers, we find the first index j // that we can't make flowers[0..j] equal to flowers[j], then we know we // can make flowers[0..j - 1] equal to flowers[j - 1]. In the meantime, // evenly increase each of them to seek a bigger min value. final int j = firstGreater(cost, i, leftFlowers); final long minIncomplete = flowers[j - 1] + (leftFlowers - cost[j - 1]) / j; ans = Math.max(ans, (long) (n - 1 - i) * full + (long) minIncomplete * partial); leftFlowers -= Math.max(0, target - flowers[i]); } return ans; } private int firstGreater(long[] A, int maxIndex, long target) { final int i = Arrays.binarySearch(A, 0, maxIndex + 1, target + 1); return i < 0 ? -i - 1 : i; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution: def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int: n = len(flowers) # If a garden is already complete, clamp it to target. flowers = [min(flower, target) for flower in flowers] flowers.sort() # All gardens are complete, so nothing we can do. if flowers[0] == target: return n * full # Have many new flowers can maximize beauty value. if newFlowers >= n * target - sum(flowers): return max(n * full, (n - 1) * full + (target - 1) * partial) ans = 0 leftFlowers = newFlowers # cost[i] := cost to make flowers[0..i] the same cost = [0] * n for i in range(1, n): # Plant (flowers[i] - flowers[i - 1]) flowers for flowers[0..i - 1]. cost[i] = cost[i - 1] + i * (flowers[i] - flowers[i - 1]) i = n - 1 # flowers' index (flowers[i + 1:] are complete) while flowers[i] == target: i -= 1 while leftFlowers >= 0: # To maximize the min # of incomplete flowers, we find the first index j # that we can't make flowers[0..j] equal to flowers[j], then we know we # can make flowers[0..j - 1] equal to flowers[j - 1]. In the meantime, # evenly increase each of them to seek a bigger min value. j = min(i + 1, bisect_right(cost, leftFlowers)) minIncomplete = flowers[j - 1] + (leftFlowers - cost[j - 1]) // j ans = max(ans, (n - 1 - i) * full + minIncomplete * partial) leftFlowers -= max(0, target - flowers[i]) i -= 1 return ans