Skip to content

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<int>& 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<long long>(target - 1) * partial);

    long long ans = 0;
    long long leftFlowers = newFlowers;
    // cost[i] := cost to make flowers[0..i] the same
    vector<long long> 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<long long>& 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