o******y 发帖数: 13 | 1 consider the process of stepping from integer x to integer y along the
integer points of the straight line. The length of each step must be non-
negative and can be one bigger than, equal to, or one smaller than the
length of the previous step.
What is the minimum number of steps in order to get from x to y? the length
of both the first and the last step must be 1.
INPUT:
the input begins with a line containing the number of test cases - n. Each
test case that follows consists of a line with two integers: 0 <= x <= y <=
2^31.
OUTPUT:
for each test case, print a line giving the minimal number of steps to get
from x to y.
Sample input:
3
45 48
45 49
45 50
Sample output:
3
3
4
很有趣的一道题:) | i**********e 发帖数: 1145 | 2 My solution:
int min_steps(int x, int y) {
int n = y-x;
if (n == 0) return 0;
int peak = (int)sqrt((double)n);
if (peak*peak == n)
return 2*peak-1;
else if (peak*(peak+1) >= n)
return 2*peak;
else
return 2*peak+1;
}
Update: 忘了检查 x==y 的特殊情况。。。加了特殊情况检测~
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|