What is the minimum number of steps in order to get from x to y? The length of the first and the last step must be 1.
Input consists of a line containing n, the number of test cases. For each test case, a line follows with two integers: 0 ≤ x ≤ y < 231. For each test case, print a line giving the minimum number of steps to get from x to y.
3 45 48 45 49 45 50
3 3 4
Source: Waterloo
Local Contest Jan. 29, 2000
在前一个数的基础上依次加若干个数，求最少需要加几个数可得到后一个数。要求加的数的序列中，起始和末尾的数为1，其他的数
比前一个大1，小1，或相等。
规律总结：
对所给的两个数的差x，若有自然数i，i(i+1)<x<=(i+1)^2，需乘2i+1个数；若有i^2<x<=i(i+1)，需乘2i个数。
#include <iostream> #include <cmath> using namespace std; int main() { int x,y,n; cin >> n; while(n--) { cin >> x >> y; int n = y-x; int q = (int)(sqrt(y-x)-1e-9); if(n<=(q+1)*q) cout<<q*2<<endl; else cout<<q*2+1<<endl; } return 0; }
原文：http://www.cnblogs.com/shenchuguimo/p/6375498.html