Steps

分析：迈开大步走当然会比较快，理想的步伐是：

1 2 3 ... N ... 3 2 1 或者 1 2 3 ... N N ... 3 2 1

但世事并非所愿，我们先来看看间距从3开始的最少步数的走法：<!--more-->

间距 步数 走法

3 3 1 1 1

4 3 1 2 1

5 4 1 2 1 1

6 4 1 2 2 1

7 5 1 2 2 1 1

8 5 1 2 2 2 1

9 5 1 2 3 2 1

10 6 1 2 3 2 1 1

11 6 1 2 3 2 2 1

12 6 1 2 3 3 2 1

13 7 1 2 3 3 2 1 1

...

以上只有在间距为4、6、9、12时，才走出了理想步伐序列。但是我们看到，间距在（4，6]的最短步数是4，（6，9]的最短步数是5，（9，12]的最短步数是6。其实，间距在(n^2, n(n+1)]区间的最短步数是2n；间距在(n(n-1), n^2]的最短步数是2n - 1。前者的理想步伐序列从

1 2 ... N N-1 ... 2 1 1 到 1 2 ... N N ... 3 2 1

后者的理想步伐序列从

1 2 ... N-1 N-1 ... 2 1 1 到 1 2 ... N-1 N ... 3 2 1

仔细观察前面给出的间距为N的步伐序列，不难得出结论。

#include <iostream>
#include <cmath>

using namespace std;

int values[] = {0, 0, 2, 3};

int steps(int d) {
  int r;
  if (d > 3) {
    int n = floor(sqrt(d));
    long long nn = n * n;
    if (nn == d)
      r = 2 * n - 1;
    else if (d <= nn + n)
      r = 2 * n;
    else
      r = 2 * n + 1;
  }
  else {
    r = values[d];
  }
  return r;
}

int main() {
  int n = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    cout << steps(y - x) << endl;
  }
  return 0;
}