Поиск минимального количества дней

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

В течение 2 тыс. Дней можно выполнить не более 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) 

Напомним, что Т (к) = к (к + 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). Как только вы найдете минимальные четные и нечетные решения, вы можете выбрать меньшее из двух.

Answer 2

AS Вы хотите иметь минимальное количество дней, вы можете просто сказать, да x + 1, так как если вы хотите минимальное количество дней, НО вы должны учитывать, что его последний день x должен быть 1, так что вам нужно перерыв в данной точке и переход на x-1, поэтому теперь мы должны определить точку останова.
точки останова находится в середине дня, так как вы начинаете на 1 и хотите закончить на 1.
Например, вы должны сделать 16 единиц таким образом вы распределяете свои дни, как:
работы сделано:
1234321 . 7 дней работы.
Если вы не можете сделать даже BreakPoint как выше повторить некоторые значения 5 = 1211
Образцы:

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

Answer 3

Если вам нужно сделать ровно N единиц, не более, то вы можете использовать динамическое программирование на матрице a [x] [y], где x - объем работы, выполненной в последний день, y - общий объем работы и a [x] [y] - минимальное количество необходимых дней. Вы можете использовать алгоритм Дейкстры, чтобы свести к минимуму [1] [N]. Начните с [1] [1] = 1.