题意简述
霓裳子突然在 $0$ 点的数字线上醒来，并拥有 $h$ 点健康值。她想到达 $d$ 点。在一个回合中，她可以做两件事中的一件：
- 在树荫下休息，并将当前健康值增加 $1$ ；
- 从当前位置 $x$ 移动到 $x + 1$ 。
每次移动都会降低霓裳子的生命值；如果是 $j$ /三次连续移动，她的生命值将减少 $j$ 点。如果移动导致霓裳子的生命值下降到 $0$ 或更低，她就无法进行移动。
例如，如果霓裳子最初的生命值为 $7$ 和 $d=4$ ，那么她的移动会如下所示：
- 从 $0$ 移动到 $1$ ，生命值减少 $1$ 。现在她在 $1$ 点，生命值为 $6$ 。
- 从 $1$ 移动到 $2$ ，并减少生命值 $2$ 。现在她位于 $2$ 点，生命值为 $4$ 。
- 从 $2$ 移动到 $3$ ，减少生命值 $3$ 。现在她位于 $3$ 点，生命值为 $1$ 。
- 休息并恢复 $1$ 点生命值。现在她位于 $3$ 点，拥有 $2$ 点生命值。
- 从 $3$ 移动到 $4$ ，并减少 $1$ 点生命值。现在她位于 $4$ 点，生命值为 $1$ 。
求她到达点 $d$ 所需的最少回合数。
思路分析
这道题最需要想到的是，假设休息 $m$ 次，最佳策略是均匀分配这 $m$ 次的休息。
一旦想到这个，就可以二分休息次数求出最少休息数了。
下为证明。
假设一个路程长度为 $L$，休息 $m$ 次，每一次在 $k_i$ 点处休息。
为了方便化简，把终点视为最后一个休息点。
那么花费的总生命即为 $\dfrac{k1(k_1-1)}{2} + \sum\limits{i=2}^{m} \dfrac{(ki-k{i-1})(ki-k{i-1}-1)}{2}$
记 $d1=k_1,\ d_i=k_i-k{i-1}\ (i=2,\dots,m)$.
那么总代价就可以化为 $\text{cost}=\dfrac{1}{2}\sum\limits_{i=1}^{m}(d_i(d_i-1))$
展开得 $\text{cost}=\dfrac{1}{2}\sum\limits_{i=1}^m d_i^2-\dfrac{L}{2}$.
因此 $L$ 固定的前提下，最小化 $\text{cost}$ 等价于最小化 $d_i$ 的平方和。
记 $\bar d = \dfrac{L}{m}$.
第一项为平方项，恒非负。第二项恒为 $0$。
则在固定和的约束下，平方和达到最小的条件即为所有 $d_i$ 满足 $d_i=\bar d$。
所以均分所消耗的代价是最小的。