algorithm - 查找最少天数

Question

我在面试中遇到了这个问题，但我仍然无法解决。是这样的

    A person has to complete N units of work; the nature of work is the same. 
In order to get the hang of the work, he completes only one unit of work in the first day. 
He wishes to celebrate the completion of work, so he decides to complete one unit of work in the last day. 
Given that he is only allowed to complete x, x+1 or x-1 units of work in a day, where x is the units of work 
completed on the previous day.
How many minimum days will he take to complete N units of work?

Sample Input:
6
-1
0
2
3
9
13

Here, line 1 represents the number of input test cases.

Sample Output:
0
0
2
3
5
7

Each number represents the minimum days required for each input in the sample input.

我尝试使用硬币找零方法进行操作，但未能成功。

Answer 1

在 2k 天内，最多可以完成 2T(k) 次工作(其中 T(k) 是第 k 个三角数)。在 2k+1 天内，最多可以完成 T(k+1)+T(k) 个工作。那是因为如果有偶数 (2k) 天，最多的工作量是 1+2+3+...+k + k+(k-1)+...3+2+1。同样，如果天数为奇数 (2k+1)，则最多的工作量为 1+2+3+...+k+(k+1)+k+...+3+2+1。

鉴于此模式，可以将工作量减少到任意值(大于 1)——只需减少工作量最大的那一天完成的工作，不要选择开始或结束日期。这永远不会使一天的工作量与相邻一天的差异不超过 1 的规则无效。

调用这个函数F。即:

F(2k)   = 2T(k)
F(2k+1) = T(k)+T(k+1)

回想一下 T(k) = k(k+1)/2，所以等式简化了:

F(2k)   = k(k+1)
F(2k+1) = k(k+1)/2 + (k+1)(k+2)/2 = (k+1)^2

根据这些观察结果，您可以通过找到至少可以完成 N 个工作单位的最少天数来解决原始问题。即最小的 d 使得 F(d) >= N。

例如，您可以使用二进制搜索来查找 d，或者最佳方法是求解方程。最小偶数解有 d/2 * (d/2 + 1) >= N，你可以用二次方程求解，最小奇数解有 (d+1)^2/4 >= N，它有解 d = ceil(2sqrt(N)-1)。找到最小偶数和奇数解后，您就可以选择两者中较小的一个。