寻找最少天数

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.

我尝试使用找零钱方法，但无法做到。

- Angersmash

---

N的限制是什么？ - Pham Trung

@PhamTrung 没有给出。我认为如果是负数，就返回0。 - Angersmash

这段内容与程序设计有关，不属于我的意见范围。请尝试将其放置在http://codegolf.stackexchange.com/上。 - Yerken

你需要完成精确的N个单位，还是至少N个单位？ - mIllIbyte

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）。一旦您找到了最小的偶数和奇数解，那么您就可以选择其中较小的一个。

- Paul Hankin

---

我仍在努力理解你的解决方案。我相信要理解这个解释需要更多的时间，比起实际问题所给的微不足道的30分钟。好吧，我想我需要更多练习。 - Angersmash

数学比我想的更难理解。试着算出在一定天数内可能完成的最大工作量，你就已经完成了95%的解决方案。 - Paul Hankin

Answer 2

如果你想要最少的天数，你只需要说是 yeah x+1，因为如果你想要最少的天数，但是你必须考虑他的最后一天x应该是1，所以你要在某个给定点中断，并且继续x-1，所以现在我们必须确定中断点。
中断点位于天数的中间，因为你从1开始，想要以1结束。
例如，你需要完成16个单位，所以你分配你的天数如下：
工作完成情况：
1234321。 共7天工作。
当你无法像上面那样做一个均匀的中断点时，请重复一些值。 5 = 1211
示例：

2: 11
3: 111
9: 12321
13: 1234321

- Johannes Geidel

Answer 3

如果您需要恰好完成N个单位的工作，则可以在矩阵a[x][y]上使用动态规划，其中x是最后一天完成的工作量，y是总工作量，a[x][y]是所需天数的最小值。您可以使用Dijkstra算法来最小化a[1][N]。从a[1][1]=1开始。

- mIllIbyte