找出步數與距離的關係即可得解。
- 0步最多能抵達的距離是0
- 1步最多能抵達的距離是1(1)
- 2步最多能抵達的距離是2(1 1)
- 3步最多能抵達的距離是4(1 2 1)
- 4步最多能抵達的距離是6(1 2 2 1)
- 5步最多能抵達的距離是9(1 2 3 2 1)
- 6步最多能抵達的距離是12(1 2 3 3 2 1)
- ……以此類推
#include <iostream>
#include <cstdio>
#include <cmath>
#define ERROR 1e-10
using namespace std;
int main(){
int n, x, y;
int dis, step;
while( scanf( "%d", &n ) != EOF ){
for( int i = ; i < n ; i++ ){
scanf( "%d%d", &x, &y ); dis = y-x;
if( dis == ){
printf( "0\n" );
continue;
} step = (int)(sqrt((double)dis)+ERROR);
if( step * step == dis ) step = step * - ;
else if( step * step + step < dis ) step = step * + ;
else step = step * ; printf( "%d\n", step );
}
}
return ;
}
另：
#include <iostream>
using namespace std; int main()
{
int x, y;
int testCases;
int min_steps = ;
cin >> testCases;
while(testCases --)
{
cin >> x >> y;
int difference = y - x;
min_steps = ; if(difference != )
{
int sumOfSteps = ;
int z = ; //divided by 2, it represents the size if the next step while(difference > sumOfSteps)
{
sumOfSteps += (z / ); // next step
min_steps ++;
z++;
}
}
cout << min_steps << endl;
}
return ;
}
#include<cstdio>
#include<cmath> int main(void)
{
int t, x, y, diff, n;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &x, &y);
diff = y - x;
if (diff == )
puts("");
else
{
n = (int)sqrt(diff);
diff -= n * n;
if (diff == )
printf("%d\n", (n << ) - );
else if (diff <= n)
printf("%d\n", n << );
else
printf("%d\n", (n << ) + );
}
}
return ;
}