uva 846 Steps

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=787

题意:从x增加到y,第一步和最后一步步长只能是1,其他步一定可以是上一步减一,和上一步相等,或者上一步步长加一,三种情况,且步长恒为正。问从x到y最少需要的步数。

思路:首先可以知道,走的最快的方法是1+2+3+…+k+…+3+2+1.这个式子的结果是一个完全平方数,为k^2,式子的长度为2*k-1.即为答案。
我们可以知道k肯定不超过 ceil(sqrt(y-x)).但是中间的k是不一定要加的。再判断k^2减去k是否已经达到结果,如果是,就将答案减一。
注意对于这种做法x=y是特殊情况。。需要特判。。。。

还有一种做法是比较好想的非数学方法。
由于对第一步和最后一步的步长有要求,都是1.
很容易想到从两边往中间走。
然后每走两步(两个方向各一步),后增加一次步长。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz