2335. Minimum Amount of Time to Fill Cups
Denote the column value as a >= b >= c
From the above formula, we can get two situations:
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.
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.
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
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, c-k, c]
[0, c-k, c-k]
[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}
$$
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 + 1, c - k, c - k]
[1, c-k, c-k]
[1, 0, 0]
So the total steps are:
$$
x + k + k + c - k + 1 = \frac{a+b+c}{2} + 1 = ceil(\frac{a+b+c}{2})
$$
1 | class Solution { |