Steps

题目描述

分析:迈开大步走当然会比较快,理想的步伐是:
1 2 3 … N … 3 2 1 或者 1 2 3 … N N … 3 2 1
但世事并非所愿,我们先来看看间距从3开始的最少步数的走法:

间距 步数 走法
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;
}

《Steps》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>