ORIGIN

LeetCode 2335. Minimum Amount of Time to Fill Cups

ACM 2 mins378 words

Problem Description

2335. Minimum Amount of Time to Fill Cups

Analysis

Denote the column value as a >= b >= c

From the above formula, we can get two situations:

  1. a >= b + c

    In this situation, we can easily get that, first, use $b$ steps, then use $c$, steps, then use $a - b - c$ steps.

    So the total steps are $a$ steps.

  2. a < b + c

    define $b := c + x$, $a := b + y = c + x + y$

    So the stones are [c+x+y, c+x, c]

    In order to achieve min steps, we should distribute the a properly to b and c.

    1. first, we use x steps to remove from the first two stones.

      Now the stones are [c+y, c, c]

      since a >= b >= c, so c+x+y < c+x + c => y < c

    2. if c+y is even

      define c+y = 2k because c+y is even.

      because y < c, so k < c

      so the stones are [2k, c, c]. So the steps are:

      • k steps for the first to stone, [k, c-k, c]
      • k steps for the first and third stone, [0, c-k, c-k]
      • c-k steps for the last two stones: [0, 0, 0]

      So in this case, the total steps are:
      $$
      x + k + k + c - k \
      = (b - c) + c + k \
      = b + k
      = b + \frac{c + y}{2} = b + \frac{c+a-b}{2} \
      = \frac{a + b + c}{2}
      $$

    3. if c+y is even

      define c+y = 2k + 1, k < c

      so the stones are [2k + 1, c, c] and the steps are:

      • k steps for first two: [k + 1, c - k, c - k]
      • k steps for first and third stone : [1, c-k, c-k]
      • c - k steps for last two: [1, 0, 0]
      • 1 step for first stone

      So the total steps are:
      $$
      x + k + k + c - k + 1 = \frac{a+b+c}{2} + 1 = ceil(\frac{a+b+c}{2})
      $$

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int fillCups(vector<int>& amount) {
int sum = 0;
int maxN = 0;
for(int i : amount) {
sum += i;
maxN = max(maxN, i);
}
return max((sum + 1) / 2, maxN);
}
};
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|